程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4756 Install Air Conditioning（次小生成樹）

HDU 4756 Install Air Conditioning（次小生成樹）

編輯：C++入門知識

HDU 4756 Install Air Conditioning（次小生成樹）

題目大意：給你n個點然後讓你求出去掉一條邊之後所形成的最小生成樹。

比較基礎的次小生成樹吧。。。先prime一遍求出最小生成樹，在dfs求出次小生成樹。

Install Air Conditioning

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1038 Accepted Submission(s): 240

Problem Description

NJUST carries on the tradition of HaJunGong. NJUST, who keeps up the ”people-Z喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcmllbnRlZCwgaGFybW9uaW91cyBkZXZlbG9wbWVudKGxIG9mIHRoZSBlZHVjYXRpb25hbCBwaGlsb3NvcGh5IGFuZCBkZXZlbG9wcyB0aGUgobF1bml0eSwgZGVkaWNhdGlvbiwgdHJ1dGgtc2Vla2luZywgaW5ub3ZhdGlvbqGxIHNjaG9vbCBtb3R0bywgaGFzIG5vdyBiZWNvbWUgYW4gZW5naW5lZXJpbmctYmFzZWQsCiBtdWx0aWRpc2NpcGxpbmFyeSB1bml2ZXJzaXR5Ljxicj4KPGJyPgogIEFzIHdlIGFsbCBrbm93LCBOYW5qaW5nIGlzIG9uZSBvZiB0aGUgZm91ciBob3R0ZXN0IGNpdGllcyBpbiBDaGluYS4gU3R1ZGVudHMgaW4gTkpVU1QgZmluZCBpdCBoYXJkIHRvIGZhbGwgYXNsZWVwIGR1cmluZyBob3Qgc3VtbWVyIGV2ZXJ5IHllYXIuIFRoZXkgd2lsbCBuZXZlciwgaG93ZXZlciwgc3VmZmVyIGZyb20gdGhhdCBob3QgdGhpcyB5ZWFyLCB3aGljaCBtYWtlcyB0aGVtIHJlYWxseSBleGNpdGVkLiBOSlVTVKGvcyA2MHRoIGJpcnRoZGF5CiBpcyBhcHByb2FjaGluZywgaW4gdGhlIG1lYW50aW1lLCA1MCBtaWxsaW9uIGlzIHNwZW50IHRvIGluc3RhbGwgYWlyIGNvbmRpdGlvbmluZyBhbW9uZyBzdHVkZW50cyBkb3JtaXRvcmllcy4gRHVlIHRvIE5KVVNUoa9zIGxvbmcgaGlzdG9yeSwgdGhlIG9sZCBjaXJjdWl0cyBhcmUgbm90IGNhcGFibGUgdG8gY2FycnkgaGVhdnkgbG9hZCwgc28gaXQgaXMgbmVjZXNzYXJ5IHRvIHNldCBuZXcgaGlnaC1sb2FkIHdpcmVzLiBUbyByZWR1Y2UgY29zdCwgZXZlcnkKIHdpcmUgYmV0d2VlbiB0d28gZG9ybWl0b3J5IGlzIGNvbnNpZGVyZWQgYSBzZWdtZW50LiBOb3csIGtub3duIGFib3V0IGFsbCB0aGUgbG9jYXRpb24gb2YgZG9ybWl0b3JpZXMgYW5kIGEgcG93ZXIgcGxhbnQsIGFuZCB0aGUgY29zdCBvZiBoaWdoLWxvYWQgd2lyZSBwZXIgbWV0ZXIsIFRvbTIwMCB3YW50cyB0byBrbm93IGluIGFkdmFuY2UsIHVuZGVyIHRoZSBwcmVtaXNlIG9mIGFsbCBkb3JtaXRvcmllcyBiZWluZyBhYmxlIHRvIHN1cHBseSBlbGVjdHJpY2l0eSwKIHRoZSBtaW5pbXVtIGNvc3QgYmUgc3BlbnQgb24gaGlnaC1sb2FkIHdpcmVzLiBBbmQgdGhpcyBpcyB0aGUgbWluaW11bSBzdHJhdGVneS4gQnV0IFRvbTIwMCBpcyBpbmZvcm1lZCB0aGF0IHRoZXJlIGFyZSBzbyBtYW55IHdpcmVzIGJldHdlZW4gdHdvIHNwZWNpZmljIGRvcm1pdG9yaWVzIHRoYXQgd2UgY2Fubm90IHNldCBhIG5ldyBoaWdoLWxvYWQgd2lyZSBiZXR3ZWVuIHRoZXNlIHR3bywgb3RoZXJ3aXNlIGl0IG1heSBoYXZlIHBvdGVudGlhbAogcmlza3MuIFRoZSBwcm9ibGVtIGlzIHRoYXQgVG9tMjAwIGRvZXNuoa90IGtub3cgZXhhY3RseSB3aGljaCB0d28gZG9ybWl0b3JpZXMgdW50aWwgdGhlIHNldHRpbmcgcHJvY2VzcyBpcyBzdGFydGVkLiBTbyBhY2NvcmRpbmcgdG8gdGhlIG1pbmltdW0gc3RyYXRlZ3kgZGVzY3JpYmVkIGFib3ZlLCBob3cgbXVjaCBjb3N0IGF0IG1vc3QgeW91"ll spend?
Input The first line of the input contains a single integer T(T ≤ 100), the number of test cases.
For each case, the first line contains two integers n(3 ≤ n ≤ 1000), k(1 ≤ k ≤ 100). n represents n-1 dormitories and one power plant, k represents the cost of high-load wire per meter. n lines followed contains two integers x, y(0 ≤ x, y ≤ 10000000), representing the location of dormitory or power plant. Assume no two locations are the same, and no three locations are on a straight line. The first one is always the location of the power plant.
Output For each case, output the cost, correct to two decimal places.
Sample Input

Sample Output

9.66
9.00

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define LL __int64
using namespace std;

const int INF = 0x3f3f3f3f;
const int maxn = 1010;
const int N = 1010;
const int M = 300010;
struct node
{
    int x, y;
} p[maxn];

struct node1
{
    int to, next;
} f[M];


int pre[N], head[N], flag[N];
int vis[N][N];
double low[N];
double dis[N][N], dp[N][N];
int n, m, num;
double sum;

void init()
{
    sum = 0;
    num = 0;
    memset(flag, 0, sizeof(flag));
    memset(vis, 0, sizeof(vis));
    memset(head, -1, sizeof(head));
    memset(dp, 0, sizeof(dp));
}


double Dis(int x0, int y0, int x1, int y1)
{
    return sqrt(1.0*(x0-x1)*(x0-x1) + 1.0*(y0-y1)*(y0-y1));
}

void add(int s, int t)
{
    f[num].to = t;
    f[num].next = head[s];
    head[s] = num ++;
}


void prime()
{
    for(int i = 1; i <= n; i++)
    {
        low[i] = dis[1][i];
        pre[i] = 1;
    }
    flag[1] = 1;
    for(int i = 1; i < n; i++)
    {
        double Min = INF;
        int v;
        for(int j = 1; j <= n; j++)
        {
            if(!flag[j] && Min > low[j])
            {
                v = j;
                Min = low[j];
            }
        }
        sum += Min;
        vis[pre[v]][v] = vis[v][pre[v]] = 1;
        add(v, pre[v]);
        add(pre[v], v);
        flag[v] = 1;
        for(int j = 1; j <= n; j++)
        {
            if(!flag[j] && low[j] > dis[v][j])
            {
                low[j] = dis[v][j];
                pre[j] = v;
            }
        }
    }
}

double dfs(int cur, int u, int fa)  //用cur更新cur點所在的子樹和另外子樹的最短距離
{
    double ans = INF;
    for(int i = head[u]; ~i; i = f[i].next) //沿著生成樹的邊遍歷
    {
        if(f[i].to == fa)
            continue;
        double tmp = dfs(cur, f[i].to, u);  //用cur更新的以當前邊為割邊的兩個子樹最短距離
        ans = min(tmp, ans);        //以(fa,u)為割邊的2個子樹的最短距離
        dp[u][f[i].to] = dp[f[i].to][u] = min(tmp, dp[u][f[i].to]);
    }
    if(cur != fa)   //生成樹邊不更新
        ans = min(ans, dis[cur][u]);
    return ans;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        init();
        scanf("%d %d",&n, &m);
        for(int i = 1; i <= n; i++) scanf("%d %d",&p[i].x, &p[i].y);
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= i; j++)
            {
                dp[i][j] = dp[j][i] = INF;
                if(i == j)
                {
                    dis[i][j] = 0.0;
                    continue;
                }
                dis[i][j] = dis[j][i] = Dis(p[i].x, p[i].y, p[j].x, p[j].y);
            }
        }
        prime();
        double ans = sum;
        for(int i = 0; i < n; i++) dfs(i, i, -1);
        for(int i = 2; i <= n; i++)
        {
            for(int j = 2; j < i; j++)
            {
                if(!vis[i][j]) continue;
                ans = max(ans, sum-dis[i][j]+dp[i][j]);
            }
        }
        printf("%.2lf\n",ans*m);
    }
    return 0;
}