Wormholes

客官°小女子只卖身不卖艺 2022-06-16 00:20 160阅读 0赞

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

YES

题目大意： 第一行 输入一个数  是表示几组测试数据

第二行  三个数 N(点的个数),M(正边的个数),W(负边的个数) 注意 ：正边为双向的，负边为单向的。

然后 M行u,v,w;

再然后W行u,v,w;

求这个图是不是存在负环。 有 YES 没NO。

#include<iostream> using namespace std; struct line { int st; int end; int time; }; line l[5200]; int d[550]; int t,i,j,k,s,e,tm,n,m,w; bool bellman_ford() { const int max=99999999; bool flag; for(i=1; i<=n; i++)//赋不赋值无所谓，这里只是判断是否存在负环，不是求最短路径 d[i]=max; d[1]=0;//加不加上没影响，因为d[i]数组只是在求某一点到其他点的最短路时才用到，而这里只是判断是不是存在负环，

//所以用不到它，所以它初不初始化都无所谓。 for(i=1; i<n; i++) { flag=0; for(j=1; j<k; j++) if(d[l[j].st]+l[j].time<d[l[j].end]) { flag=1; d[l[j].end]=d[l[j].st]+l[j].time; } //cout<<d[i]<<endl; if(!flag) break; } for(i=1; i<k; i++) if(d[l[i].st]+l[i].time<d[l[i].end]) return false; return true; } int main() { cin>>t; while(t--) { cin>>n>>m>>w; k=1; for(i=1; i<=m; i++) { cin>>s>>e>>tm; l[k].st=s; l[k].end=e; l[k].time=tm; k++; l[k].st=e; l[k].end=s; l[k].time=tm; k++; } for(i=1; i<=w; i++) { cin>>s>>e>>tm; l[k].st=s; l[k].end=e; l[k].time=-tm; k++; } if(!bellman_ford()) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; } #include <iostream> #include <cstring> using namespace std; const int MAX = 9999999; int f; int n; int m; int w; int edgeNum;//边的条数 typedef struct { int v1;//边的起点 int v2;//边的终点 int w;//边的权值 } Edge; Edge e[5201]; bool bellmanFord() { bool flag; int i,j; int d[501]; d[1]=0; for(i = 2; i <= n; i++) d[i] = MAX; for(i = 1; i <= n; i++) { flag = false; for(j = 1; j <= edgeNum; j++) { if(d[e[j].v1] != MAX && d[e[j].v1] + e[j].w < d[e[j].v2]) { d[e[j].v2] = d[e[j].v1] + e[j].w; flag = true; } } if(!flag) break; } if(i == n + 1) return true; else return false; } int main() { int i,j,p,q,w1; cin>>f; for(i = 0; i < f; i++) { edgeNum = 0; memset(e,0,sizeof(e)); cin>>n>>m>>w; for(j = 1; j <= m; j++)//双向边的输入 { edgeNum ++; cin>>p>>q>>w1; e[edgeNum].v1 = p; e[edgeNum].v2 = q; e[edgeNum].w = w1; edgeNum ++; e[edgeNum].v1 = q; e[edgeNum].v2 = p; e[edgeNum].w = w1; } for(j = 1; j <=w; j++)//单向边的输入 { edgeNum ++; cin>>p>>q>>w1; e[edgeNum].v1 = p; e[edgeNum].v2 = q; e[edgeNum].w = (-1)*w1; } if(bellmanFord()) cout<<"YES\n"; else cout<<"NO\n"; } return 0; } #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int VM=520; const int EM=2520; const int INF=0x3f3f3f3f; struct node{ int u,v; int cap; }edge[EM<<1]; int n,m,k; int cnt,dis[VM]; void addedge(int cu,int cv,int cw){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].cap=cw; cnt++; } int Bellman_ford(){ int i,j; for(i=1;i<=n;i++) dis[i]=INF; dis[1]=0; for(i=1;i<=n;i++){ int flag=0; for(j=0;j<cnt;j++) if(dis[edge[j].v]>dis[edge[j].u]+edge[j].cap){ dis[edge[j].v]=dis[edge[j].u]+edge[j].cap; flag=1; } if(!flag) //优化 break; } return i==n+1; //相等则存在正环 } int main(){ //freopen("input.txt","r",stdin); int t; scanf("%d",&t); while(t--){ scanf("%d%d%d",&n,&m,&k); cnt=0; int u,v,w; while(m--){ scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } while(k--){ scanf("%d%d%d",&u,&v,&w); addedge(u,v,-w); } int ans=Bellman_ford(); printf("%s\n",ans==1?"YES":"NO"); } return 0; }