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

Re:虽然是用kruskal的,因没考虑-1,wa一次,囧。。

Posted by howling at 2011-07-20 13:12:56 on Problem 2377
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:
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