與這個題基本一樣。
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;
}