首页 > 代码库 > poj-3259-wormholes-spfa-判负环

poj-3259-wormholes-spfa-判负环

2024-07-13 17:41:34   226人阅读

题意：N个顶点， M条双向边， W条权值为负的单向边。求是否存在负环。

思路：首先你要懂bellman-ford或spfa。。这是基础的spfa判断是否存在负环的题，存在负环的节点会重复入队（因为最短路在不断变小）， 所以只要有节点重复入队超过n次，即可判断存在负环（即开一个数组记录节点入队次数）。

 

总结：本来是想求出每对节点之间的最短路，看是否存在负的，结果果断TLE。后来才想起spfa可以处理负环云云~~

AC代码：

 1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<algorithm> 5 #include<vector> 6 #include<climits> 7 #include<cstring> 8 using namespace std; 9 #define maxn 60010 #define INF 1000000011 struct node12 {13    int to, dist;14 };15 vector<node> g[maxn];16 int n, m, w;17 int cnt[maxn], d[maxn];18 void input()19 {20    scanf("%d%d%d", &n, &m, &w);21    for(int i = 0; i < n+10; i++) g[i].clear();22    for(int i = 0; i < m; i++){23       int a, b, c;24       scanf("%d%d%d", &a, &b, &c);25       g[a].push_back((node){b, c});26       g[b].push_back((node){a, c});27    }28    for(int i = 0; i < w; i++) {29       int a, b, c;30       scanf("%d%d%d", &a, &b, &c);31       c = -c;32       g[a].push_back((node) {b, c});33    }34 }35 bool spfa(int s)36 {37    for(int i = 0; i <= n; i++) d[i] = INF, cnt[i] = 0;38    d[s] = 0;39    cnt[s] = 1;40    queue<int> q;41    q.push(s);42    bool inq[maxn]; memset(inq, 0, sizeof(inq));43    inq[s] = true;44    while(!q.empty()){45       int t = q.front(); q.pop();46       inq[t] = false;47       int l = g[t].size();48       for(int i = 0; i < l; i++){49          int to = g[t][i].to, dist = g[t][i].dist;50          if(d[to] > d[t] + dist) {51             d[to] = d[t] + dist;52             if(!inq[to]){53                inq[to] = 1;54                cnt[to]++;55                if(cnt[to] >= n) return true;56                q.push(to);57             }58          }59       }60    }61    return false;62 }63 void work()64 {65    input();66    if(spfa(1)) printf("YES\n");67    else printf("NO\n");68 }69 70 int main()71 {72    int t ; cin>>t;73    while(t--){74       work();75    }76    return 0;77 }
View Code


联系
我们