POJ - 3259 Wormholes (弗洛伊德、Bellman-Ford)

约定不等于承诺〃 2022-05-17 22:59 185阅读 0赞

#                                          Wormholes #

### Description ###

While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ's farms comprises *N* (1 ≤ *N* ≤ 500) fields conveniently numbered 1..*N*, *M* (1 ≤ *M* ≤ 2500) paths, and *W* (1 ≤ *W* ≤ 200) wormholes.

As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .

To help FJ find out whether this is possible or not, he will supply you with complete maps to *F* (1 ≤ *F* ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.

Input

Line 1: A single integer, *F*. *F* farm descriptions follow.  
Line 1 of each farm: Three space-separated integers respectively: *N*, *M*, and *W*  
Lines 2..*M*\+1 of each farm: Three space-separated numbers (*S*, *E*, *T*) that describe, respectively: a bidirectional path between *S* and *E* that requires *T* seconds to traverse. Two fields might be connected by more than one path.  
Lines *M*\+2..*M*\+*W*\+1 of each farm: Three space-separated numbers (*S*, *E*, *T*) that describe, respectively: A one way path from *S* to *E* that also moves the traveler back *T* seconds.

### Output ###

Lines 1..*F*: For each farm, output "YES" if FJ can achieve his goal, otherwise output "NO" (do not include the quotes).

### Sample Input ###

2  
3 3 1  
1 2 2  
1 3 4  
2 3 1  
3 1 3  
3 2 1  
1 2 3  
2 3 4  
3 1 8

### Sample Output ###

NO  
YES

### Hint ###

For farm 1, FJ cannot travel back in time.  
For farm 2, FJ could travel back in time by the cycle 1->2->3->1, arriving back at his starting location 1 second before he leaves. He could start from anywhere on the cycle to accomplish this.

**题意描述：**  
判断是否为负权回路，第一行为n，m，w; n为n个点m为m条正权且是双向的，w为w条负权是单向的；下面先是m行正权边，再是w行负权边判断能否构成负权回路。（一个人在一个n个点的地方m条普通的路a,b,c从a到b或从b到a花费c时间，w个虫洞，a,b,c，能将人从a地点传送到b点时间倒流c；问是否存在从一个地点到另一个地点在经过虫洞回到刚开始的地点且时间更向前）

**解题思路：**

弗洛伊德和Bellman-Ford算法都能实现注意正权边是是双向的，负权边是单向的。

弗洛伊德：

#include<stdio.h>
    #include<string.h>
    # define inf 99999999
    int map[510][510],book[510],dis[510];
    int main()
    {
    	int n,m,i,j,k,w,t,a,b,c,f;
    	int S[210],E[210],T[210];
    	while(scanf("%d",&t)!=EOF)
    	{
    		while(t--)
    		{
    			scanf("%d%d%d",&n,&m,&w);
    			for(i=1;i<=n;i++)
    				for(j=1;j<=n;j++)
    				{
    					if(i==j)
    						map[i][j]=0;
    					else
    						map[i][j]=inf;
    				}
    			while(m--)
    			{
    				scanf("%d%d%d",&a,&b,&c);
    				if(map[a][b]>c)
    				{
    					map[a][b]=c;
    					map[b][a]=c;
    				}
    			}
    			for(i=1;i<=w;i++)//存入负权边 
    			{
    				scanf("%d%d%d",&a,&b,&c); 
    				map[a][b]=-c;
    			}
    			f=0;
    			for(k=1;k<=n;k++)//利用弗洛伊德算法 
    			{
    				for(i=1;i<=n;i++)
    				{
    					for(j=1;j<=n;j++)
    						if(map[i][j]>map[i][k]+map[k][j])
    						{
    							map[i][j]=map[i][k]+map[k][j];
    						}
    					if(map[i][i]<0)//如果自己到本身的时间变为了负，说明构成了负权回路，他可以回到之前的时间之前的位置 
    					{
    						f=1;
    						break;
    					} 	
    				}
    				if(f==1)//若找到就跳出，不在继续寻找，否则会超时 
    					break;
    			}	
    			if(f==1)
    				printf("YES\n");
    			else
    				printf("NO\n");
    		}
    	}
    	return 0;
    }

Bellman-Ford:

#include<stdio.h>
    #include<string.h>
    # define inf 99999999
    int dis[510];
    int main()
    {
    	int n,m,i,j,w,t,a[3510],b[3510],c[3510],f,k;
    	while(scanf("%d",&t)!=EOF)
    	{
    		while(t--)
    		{
    			scanf("%d%d%d",&n,&m,&w);
    			for(i=1;i<=m;i++)
    				scanf("%d%d%d",&a[i],&b[i],&c[i]);
    			for(i=m+1;i<=w+m;i++)
    			{
    				scanf("%d%d%d",&a[i],&b[i],&c[i]);
    				c[i]=-c[i];
    			}
    			for(i=1;i<=n;i++)
    				dis[i]=inf;
    			dis[1]=0;
    			for(i=1;i<n;i++)
    			{
    				k=0;
    				for(j=1;j<=m+w;j++)
    				{
    					if(j<=m)//判断正权边双向判断 
    					{
    						if(dis[a[j]]>dis[b[j]]+c[j])
    						{
    							dis[a[j]]=dis[b[j]]+c[j];
    							k=1;
    						}
    						else if(dis[b[j]]>dis[a[j]]+c[j])
    						{
    							dis[b[j]]=dis[a[j]]+c[j];
    							k=1;
    						}
    					}
    					else if(j>m)//判断负权边，单向 
    					{
    						if(dis[b[j]]>dis[a[j]]+c[j])
    						{
    							dis[b[j]]=dis[a[j]]+c[j];
    							k=1;
    						}
    					}
    					
    				}
    					
    				if(k==0)
    					break;		
    			}
    			f=0;
    			for(i=1;i<=m+w;i++)
    			{
    				if(j<=m)
    				{
    					if(dis[a[i]]>dis[b[i]]+c[i])
    					{
    						f=1;
    						break;
    					}
    					if(dis[b[i]]>dis[a[i]]+c[i])
    					{
    						f=1;
    						break;
    					}	
    				}
    				if(j>m)
    					if(dis[b[i]]>dis[a[i]]+c[i])
    					{
    						f=1;
    						break;
    					}
    				
    			}
    			if(f==1)
    				printf("YES\n");
    			else
    				printf("NO\n");
    		}
    	}
    	return 0;
    }