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

Posted by leila_n at 2008-12-22 13:24:18 on Problem 2377
In Reply To:prim Posted by:azma at 2008-12-22 13:19:34
> #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=-1000000000;
> 	s[1]=true;
> 	for(i=2;i<=n;i++)
> 	{ 
> 		Distance[i]=W[1][i];
> 		nearest[i]=1;
> 		s[i]=false;
> 	} 
> 	for(i=1;i<n;i++)
> 	{
> 		max=-1000000000;
> 		j=1;
> 		for(k=2;k<=n;k++)
> 		if(!s[k]&&Distance[k]>max)
> 		{ 
> 			max=Distance[k];
> 			j=k;
> 		} 
> 		T+=W[j][nearest[j]];
> 		if(nearest[j]<1)
> 		{ 
> 			flag=false;
> 			return;
> 		} 
> 		s[j]=true;
> 		for(k=2;k<=n;k++)
> 			if(!s[k]&&W[k][j]>Distance[k])
> 			{ 
> 				Distance[k]=W[k][j];
> 				nearest[k]=j;
> 			} 
> 	} 
> } 
> 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]=-1000000000;
> 	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