| ||||||||||
| 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