1090. Highways

TAG 最小生成树 Kruskal

用Kruskal求最小生成树，最后加入的边的长度就是结果。

证明一下为什么可以这么求。

题目要求图要连通，可以有环，且最长边最小。

Kruskal保证图是连通无环的，且全部的边的和最小。

题目允许有环，而在进行Kruskal时那些会形成环的边会被丢弃，但其长度小于等于最后加入的边的长度，对结果无影响。并且Kruskal求解的基础就是“用小的边能保证最终生成的边的和最小”（具体证明参见Kruskal算法），所以能满足最后加入的边长度是最小。

囧。又Presentation error了。。有些在每个case之后空行，有些只能在case之间空行。。

/* source code of submission 431637, Zhongshan University Online Judge System */
#include <stdio.h>
#include <algorithm>
using namespace std;
struct node
{
    int v,u,dist;
    bool operator<(const node &y)const
    {
        return dist<y.dist;
    }
};
node edge[500*499/2];
int nedge;
int n,m,t;
int tmp,ans;
int par[500];
int find(int x)
{
    if ( x==par[x] )
    {
        return x;
    }
    else
    {
        par[x]=find(par[x]);
        return par[x];
    }
}
int main(int argc, char *argv[])
{
    scanf("%d", &t);
    while ( t-- )
    {
        nedge=-1;
        scanf("%d", &n);
        for (int i=0; i<n; ++i)
        {
            for (int j=0; j<n; ++j)
            {
                scanf("%d", &tmp);
                if ( j>i )
                {
                    ++nedge;
                    edge[nedge].v=i;
                    edge[nedge].u=j;
                    edge[nedge].dist=tmp;
                }
            }
        }
        sort(edge, edge+nedge+1);
        for (int i=0; i<n; ++i)
        {
            par[i]=i;
        }
        m=0; 
        ans=0;
        for (int i=0; i<=nedge; ++i)
        {
            if ( find( edge[i].v) != find(edge[i].u) )
            {
                ++m;
                ans=edge[i].dist;
                par[ find(edge[i].v) ]=par[ edge[i].u ];
                if ( m==(n-1) )
                {
                    break;
                }
            }
        }
        printf("%d/n",ans );
        if ( t!=0 )
        {
            printf("/n");
        }
    }
    
    return 0;
}