#include<stdio.h>
#include<algorithm>
#include<string.h>
#define ll long long
using namespace std;
const int MYDD=1103+1e4;

int set[MYDD];
void init(int x) {//并查集的初始化
	for(int j=1; j<=x; j++)
		set[j]=j;
}

int find(int x) {//并查集的查操作
	int t,child=x;
	while(x!=set[x])
		x=set[x];
	while(child!=x) {//路径压缩
		t=set[child];// t 记录当前父节点
		set[child]=x;
		child=t;
	}
	return x;
}

bool combine(int x,int y) {//并查集的并操作
	int fx=find(x);
	int fy=find(y);
	if(fx!=fy) {
		set[fx]=fy;
		return true;//不成环
	}
	return false;
}

struct EDGE {
	int u,v,w,vis;//vis 标记当前节点是否已经有边
} edge[MYDD*2];
bool cmp(EDGE x,EDGE y) {
	return x.w<y.w;
}

int main() {
	int n;
	while(scanf("%d",&n)!=EOF) {
		init(n);
		int dd=1;
		for(int j=1; j<=n; j++) {
			for(int k=1; k<=n; k++) {
				edge[dd].u=j;
				edge[dd].v=k;//边的存储 
				scanf("%d",&edge[dd].w);
				edge[dd].vis=0;
				dd++;
			}
		}

		sort(edge+1,edge+dd+1,cmp);//数据处理

		ll ans=0;//记录答案 
		int count=0;
		for(int j=1; j<=dd; j++) {//这里用count统计运行错误 
			if(combine(edge[j].u,edge[j].v)) {
				ans+=edge[j].w;
				count++;
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}

• Re:挂了好多次，为什么就是继续挂，求参考 (6) yygy 2016-08-08 13:09:56