Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:虽然是用kruskal的,因没考虑-1,wa一次,囧。。In Reply To:Re:虽然是用kruskal的,因没考虑-1,wa一次,囧。。 Posted by:rayafjyblue at 2010-12-08 00:29:31 出现重边又怎么样?那不可能是重边不一样的权值啊? #include<iostream> using namespace std; const int N = 1002; int W[N][N],Distance[N]; int nearest[N],n,T = 0; bool s[N],flag=true; void prim(void) { int i,j,k; int max=-100; s[1]=true; for(i=2;i<=n;i++) { Distance[i]=W[1][i]; s[i]=false; } for(i=1;i<n;i++) { max=-100; j=1; for(k=2;k<=n;k++) if(!s[k]&&Distance[k]>max) { max=Distance[k]; j=k; } T+=max; s[j]=true; for(k=2;k<=n;k++) if(!s[k]&&W[k][j]>Distance[k]) { Distance[k]=W[k][j]; } } for(int q=1;q<=n;q++)if(s[q]==false)flag=false; } int main(){ int i,a,b,c,m; cin>>n>>m; for(a=1;a<=n;a++) for(b=1;b<=n;b++) W[a][b]=-100; for(i=1;i<=m;i++) { cin>>a>>b>>c; if(W[a][b]<c)//这是为什么啊????????? W[a][b]=W[b][a]=c; } prim(); if(flag)cout<<T<<endl;else cout<<-1<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator