题目描述
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
Output
NO YES
思路:块田就是图中的点,其中路径是双向的,虫洞是单向的.题目的要求是看能不能找到回到起点时,时间在出发时间之前.
主要还是判断图中有没有负环,并且在回到自己起点时,时间是不是负的.
可以使用Bellman-Ford或者SPFA.
举例:
1.如下图,FJ返回1号时,正好为0.不满足题意.
两种方法的代码如下:
代码:Bellman-Ford
#include<iostream> #include<string.h> using namespace std; int n,m,W; const int maxn = 510; const int INF = 0x3f3f3f3f; int u[maxn],v[maxn],w[maxn],dis[maxn],flag,num; void add(int u1,int v1,int w1){ u[num] = u1; v[num] = v1; w[num] = w1; num++; } bool Ford(int s){ for(int i = 1; i <=n ;i++){ dis[i] = INF; } dis[s] = 0; for(int i = 0; i < n-1; i++){ flag = 0; for(int j = 0; j < num; j++){ if(dis[v[j]]>dis[u[j]]+w[j]){ dis[v[j]] = dis[u[j]] + w[j]; flag = 1; } } if(!flag){ break;//不存在负环 } } for(int j = 0; j < num; j++){ if(dis[v[j]]>dis[u[j]]+w[j]){ //dis[v[j]] = dis[u[j]] + w[j]; return true; } } return false; } int main() { int T,uu,vv,ww; cin>>T; while(T--){ num = 0; cin>>n>>m>>W; for(int i = 0; i < m; i++){ cin>>uu>>vv>>ww; add(uu,vv,ww); add(vv,uu,ww); } for(int i = 0; i < W; i++){ cin>>uu>>vv>>ww; add(uu,vv,-ww); } if(Ford(1)){ cout<<"YES"<<endl; }else{ cout<<"NO"<<endl; } } }
SPFA
#include<iostream> #include<queue> #include<string.h> using namespace std; int n,m,W,num; const int maxn = 510,maxe=6000; const int INF = 0x3f3f3f3f; int head[maxn],vis[maxn],dis[maxn],sum[maxn]; struct Edge { int next,to,w; } e[maxe]; void add(int u,int v,int w) { e[++num].next = head[u]; e[num].to = v; e[num].w = w; head[u] = num; } bool spfa(int u) { queue<int> q; memset(vis,0,sizeof(vis)); memset(sum,0,sizeof(sum)); dis[u] = 0; sum[u]++; q.push(u); vis[u] = 1; while(!q.empty()) { int x = q.front(); q.pop(); vis[x] = 0; for(int i = head[x]; i; i = e[i].next) { int v = e[i].to; if(dis[e[i].to] > dis[x]+e[i].w) { dis[e[i].to] = dis[x]+e[i].w; if(!vis[e[i].to]) { //判断是否在队列内,如果不再就让sum进行++,说明改点又被松弛了一次. sum[e[i].to]++; q.push(e[i].to); vis[e[i].to] = 1; if(sum[e[i].to] >= n) { //判断节点松弛次数是否超过了n return true; } } } } } return false; } int main() { int T,u,v,w; cin>>T; while(T--) { cin>>n>>m>>W; num = 0; for(int i = 1; i <= n; i++) { //dis进行初始化 dis[i] = INF; } memset(head,0,sizeof(head)); for(int i = 0; i < m; i++) { cin>>u>>v>>w; add(u,v,w); add(v,u,w); } for(int i = 0; i < W; i++) { cin>>u>>v>>w; add(u,v,-w);//他是一条负边. } if(spfa(1)) {//存在负环 cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } } return 0; }
