HDU4081 Qin Shi Huang's National Road System【Kruska】【次小生成树】

2011 Asia Beijing Regional Contest

题目大意：有N个城市，秦始皇要用N-1条路将他们全部连起来，秦始皇希望这N-1条路长度

之和最短。这时候，徐福跳出来说他有魔法，可以凭空变出其中任意一条路来。

秦始皇希望徐福将N-1条路中最长的那条路变出来，但是徐福希望把修路要求人数最多的那条

路变出来(每条路修路的人力是两座城市的人口和)。最终，秦始皇给出了一个公式 A/B

徐福变出的那条路所需人力/除了这条路之外的N-2条路的和   最大。

简化大意为：给你N个城市的坐标(x,y)和人口。 得到他的最小生成树之后，去掉最小生成树上

的一条边，使得这条路两边连接城市的人数和/最小生成树上其他N-2条路的长度和(A/B)最大。

输出这个最大的比值。

思路：为了使得上述公式A/B比值最大，就需要B尽可能小。

先求出最小生成树MST，再选择要删去哪一条边，可以遍历MST上的边，假设枚举的边长度为

Len[i][j]，最终结果就为max(A/MST-Len[i][j])(1<=i<=n,i+1<=j<=n)。其中A为最小生成树

上的边。若A不是最小生成树上的边。最小生成树加上A边就会成为一个环。为了使得他原先为

一个生成树，就要删去这个环上除了A边外权值最大的边，就是原先最小生成树中权值最大的边。

最终结果还是max(A/MST-Len[i][j])(1<=i<=n,i+1<=j<=n)。而加上A边所形成的生成树其实

就是次小生成树。所以问题就转换为求次小生成树，再遍历求结果。

注意：代码用C++提交就超时，G++提交就AC。不知道什么情况。。。按理说C++比G++高效

才对。不知道是什么原因~求大神给解释解释哈~感激不尽。

参考博文：http://tech.ddvip.com/2013-10/1380576235203623.html

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXN = 1010;
const int MAXM = 1000010;

int father[MAXN];
int find(int x)
{
    if(x != father[x])
        father[x] = find(father[x]);
    return father[x];
}

struct Node
{
    int from;
    int to;
    double w;
};

Node Edges[MAXM];

bool cmp(Node a,Node b)
{
    return a.w < b.w;
}

struct Node1
{
    int to;
    int next;
};

Node1 Vertex[MAXN];

struct Node2
{
    int x;
    int y;
    double d;
};
Node2 Point[MAXN];

double Dist(int i,int j)
{
    double x = Point[i].x - Point[j].x;
    double y = Point[i].y - Point[j].y;
    return sqrt(x*x+y*y);
}
int N,M,Head[MAXN],End[MAXN];
double Len[MAXN][MAXN];

double Kruskal()
{
    int i,x,y,w,v,k = 0;
    double ans = 0;
    for(i = 1; i <= N; ++i)
    {
       Vertex[i].to = i;
       Vertex[i].next = -1;
       Head[i] = End[i] = i;
    }
    for(i = 0; i < M; ++i)
    {
        if(k == N-1)
            break;
        if(Edges[i].w < 0)
            continue;
        x = find(Edges[i].from);
        y = find(Edges[i].to);
        if(x != y)
        {
            for(w = Head[x]; w != -1; w = Vertex[w].next)
            {
                for(v = Head[y]; v != -1; v = Vertex[v].next)
                {
                    Len[Vertex[w].to][Vertex[v].to] = Len[Vertex[v].to][Vertex[w].to] = Edges[i].w;
                }
            }
            father[y] = x;//改为father[x] = y就错
            Vertex[End[y]].next = Head[x];
            Head[x] = Head[y];
            k++;
            ans += Edges[i].w;
            if(k == N-1)
                break;
        }
    }
    return ans;
}

double maxv(double a,double b)
{
    return a > b ? a : b;
}

int main()
{
    int T,i,j;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&N);
        for(i = 1; i <= N; ++i)
            father[i] = i;
        for(i = 1; i <= N; ++i)
        {
            scanf("%d%d%lf",&Point[i].x,&Point[i].y,&Point[i].d);
        }
        M = 0;
        for(i = 1; i <= N; ++i)
        {
            for(j = i+1; j <= N; ++j)
            {
                Edges[M].from = i;
                Edges[M].to = j;
                Edges[M++].w = Dist(i,j);
            }
        }
        sort(Edges,Edges+M,cmp);
        double MST = Kruskal();
        double ans = 0;
        for(i = 1; i <= N; ++i)
        {
            for(j = i+1; j <= N; ++j)

                ans = maxv(ans,(Point[i].d + Point[j].d)/(MST-Len[i][j]));
        }
        printf("%.2lf\n",ans);
    }

    return 0;
}

HDU4081 Qin Shi Huang's National Road System【Kruska】【次小生成树】

原文：http://blog.csdn.net/lianai911/article/details/42218969