POJ:2421 Constructing Roads

与这个题基本一样。

http://blog.csdn.net/kkkwjx/article/details/12316701

最小生成树的题要搞清楚点的个数，边的个数，不要混了。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define MAXN 10005
using namespace std;
struct Edge
{
    int a,b,weight;
};
int father[105];
int find(int p)
{
    return p==father[p]?p:(father[p]=find(father[p]));
}
bool cmp(Edge x,Edge y)
{
    return x.weight<y.weight;
}
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {

        Edge p[MAXN];
        int id=0;
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
            {
                int val;
                scanf("%d",&val);
                if(i==j) continue;
                p[id].a=i;
                p[id].b=j;
                p[id++].weight=val;
            }
        for(int i=0; i<=n; ++i)
            father[i]=i;
        int m;
        scanf("%d",&m);
        int N;
        if(m%2) N=(m+1)/2*m;
        else N=m/2*(m+1);
        for(int i=0; i<N; ++i)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            u=find(u);
            v=find(v);
            father[u]=v;
        }
        sort(p,p+id,cmp);
        int ans=0;
        for(int i=0; i<id; ++i)
        {
            int ta=find(p[i].a),tb=find(p[i].b);
            if(ta!=tb)
            {
                father[ta]=tb;
                ans+=p[i].weight;
            }
        }
        printf("%d\n",ans);

    }
    return 0;
}