记录编号	127258	评测结果	AAAAA
题目名称	[Tyvj Aug11] 冗余电网	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.166 s
提交时间	2014-10-15 08:15:16	内存使用	3.34 MiB

#include<algorithm>
#include<cstdio>
using namespace std;
struct dx
{
	int s;
	int e;
	int data;
};
dx h[200001];
int n,m,k;
int x,y,z;
int f[200001];
long long tot;
int find(int x)
{
	if(f[x]==x)	return x;
	f[x]=find(f[x]);
	return f[x];
}
bool comp(dx a,dx b)
{
	return a.data<b.data;
}
int main()
{
	freopen("ugrid.in","r",stdin);
	freopen("ugrid.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		h[i].s=x;
		h[i].e=y;
		h[i].data=z;
	}
	sort(h+1,h+m+1,comp);
	for(int i=1;i<=m;i++)
	{
		x=find(h[i].s);
		y=find(h[i].e);
		if(x!=y)
		{
			tot+=h[i].data;
			f[x]=y;
		}
	}
	bool flag=0;
	int sum=0;
	k=find(k);
	for(int i=1;i<=n;i++)
	{
		x=find(i);
		if(x!=k) {flag=1;sum++;}
	}
	if(flag) printf("%d",sum);
	else printf("%lld",tot);
	return 0;
}