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
北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

啊,我快受不了,谁帮我找一组WA的测试数据?

Posted by maths at 2005-10-04 00:52:29 on Problem 2631
#include <stdio.h>
#include <stdlib.h>
#define max 10005
typedef struct villageinf
{	int a;
	int b;
	int dis;
}village;
int main(void)
{	village road[max];
	int i,j,n,k,largersum;
	int node[max];
	int num[max];
	memset(road,0,sizeof(road));
	memset(num,0,sizeof(num));
	memset(node,0,sizeof(node));
	n=0;
	while(scanf("%d%d%d",&road[n].a,&road[n].b,&road[n].dis)!=EOF) 
	{	if(road[n].a==0&&road[n].b==0) break;
		num[road[n].a]++;
		num[road[n].b]++;
		n++;
	}
	/*for(i=0;i<n;i++)
		printf("%d %d %d\n",road[i].a,road[i].b,road[i].dis);*/
	k=0;largersum=0;
	//printf("%d\n",n);
	while(k<=n-2)
	{	for(i=0;i<n;i++)
		{	if(num[road[i].a]==1&&num[road[i].b]>0)
			{	num[road[i].a]=0;
				if(largersum<node[road[i].b]+road[i].dis+node[road[i].a])
					largersum=node[road[i].b]+road[i].dis+node[road[i].a];
				if(node[road[i].b]<road[i].dis+node[road[i].a])
					node[road[i].b]=road[i].dis+node[road[i].a];
				road[i].dis=0;
				num[road[i].b]--;
				k++;
				//printf("%d,%d,%d,%d\n",road[i].a,node[road[i].b],road[i].b,k);
				if(k==n-1)
					break;
			}
			else if(num[road[i].b]==1&&num[road[i].a]>0)
			{	num[road[i].b]=0;
				if(largersum<node[road[i].b]+road[i].dis+node[road[i].a])
					largersum=node[road[i].b]+road[i].dis+node[road[i].a];
				if(node[road[i].a]<road[i].dis+node[road[i].b])
					node[road[i].a]=road[i].dis+node[road[i].b];
				road[i].dis=0;
				num[road[i].a]--;
				k++;
				//printf("%d,%d,%d,%d\n",road[i].b,node[road[i].a],road[i].a,k);
				if(k==n-1)
					break;
			}
		}
	}
	for(i=0;i<n;i++)
		if(road[i].dis>0)
		{	if(largersum<=node[road[i].a]+node[road[i].b]+road[i].dis)
				printf("%d\n",node[road[i].a]+node[road[i].b]+road[i].dis);
			else printf("%d\n",largersum);
			break;
		}
	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