Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Kruscal无敌,不用考虑重边,输出-1的时候只要加一个特判就可以了

Posted by zhouzhendong at 2017-02-26 12:03:16 on Problem 2377
47MS

#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long ll;
struct edge{
	ll a,b,len;
}e[21000];
ll n,m,fa[1100];
bool cmp(edge a,edge b){
	return a.len>b.len;
}
ll getf(ll k){
	if (fa[k]==k) return k;
	fa[k]=getf(fa[k]);
	return fa[k];
}
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].len);
	std::sort(e+1,e+1+m,cmp);
	for (int i=1;i<=n;i++)
		fa[i]=i;
	ll ez=0,ans=0;
	for (int i=1;ez<n-1&&i<=m;i++){
		if (getf(e[i].a)==getf(e[i].b))
			continue;
		ans+=e[i].len;
		ez++;
		fa[getf(e[i].a)]=getf(e[i].b);
	}
	if (ez==n-1)
		printf("%lld",ans);
	else printf("-1");
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator