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:改成这样了 还不行

Posted by tangbohu222 at 2011-04-02 21:08:29 on Problem 1797
In Reply To:求助啊 利用prim算法变形做的 就是错啊 谁帮忙看看啊 或者提供点测试数据啊 Posted by:tangbohu222 at 2011-04-02 20:48:45
#include <stdio.h>
long int dist[1005][1005];
long int low[1005];
int sce,m,n;
const long int MAX=10000000;
long int  prim_1()
{
	long int  ans=0;
	for (int i=1;i<=n;i++)
	{
		low[i]=dist[1][i];
	}
	low[1]=0;
	for (int i=1;i<=n;i++)
	{
		long int MIN=MAX;
		int t=0;
		for (int j=1;j<=n;j++)
		{
			if((low[j]!=0)&&(low[j]<MIN))
			{
				MIN=low[j];
				t=j;
				
			}
		}
		if (t)
		{
			if(MIN>ans)
				ans=MIN;
			low[t]=0;
			for(int j=1;j<=n;j++)
			{
				if (low[j]&&dist[t][j]<low[j])
				{
					low[j]=dist[t][j];
				}
			}
		}
	}
	return ans;
}
int main()
{
	//freopen("C:/Users/bohu/Desktop/a.in","r",stdin);
	int t1,t2;
	scanf("%d",&sce);
	for(int i=1;i<=sce;i++)
	{
		scanf("%d%d",&n,&m);
		for (int j=1;j<=n;j++)
		{
			for(int h=1;h<=n;h++)
				dist[j][h]=MAX;
		}
		for (int j=1;j<=m;j++)
		{
			scanf("%d%d",&t1,&t2);
			scanf("%ld",&dist[t1][t2]);
			dist[t2][t1]=dist[t1][t2];
		}
		printf("Scenario #%d:\n",sce);
		printf("%ld\n\n",prim_1());


	}
	//fclose(stdin);
	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