本文主要是介绍uvalive 6800 - The Mountain of Gold? 判负环，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给出一个图，判断能不能从0出发，再回到0，经过边的权值为负。
判断图中有没有负环，并且负环上的点能回到0即可。
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 1000 + 10;
int dist[maxn];
struct Edge{int u, v, cost;Edge(){}Edge(int u, int v, int cost) : u(u), v(v), cost(cost) {}
};
vector<Edge> e;
vector<int> ee[1005];
int vis[1005];
int dfs(int u) {if(u == 0)return 1;vis[u] = 1;for(int i = 0; i < ee[u].size(); i++) {if(!vis[ee[u][i]])if(dfs(ee[u][i]))return 1;}return 0;
}
bool bellman_ford(int s, int n){for(int i = 0; i < n; ++i) dist[i] = INF;dist[s] = 0;for(int i = 1; i < n; ++i){bool flag = false;for(int j = 0; j < e.size(); ++j){int u = e[j].u; int v = e[j].v;int cost = e[j].cost;if(dist[v] > dist[u] + cost){dist[v] = dist[u] + cost;flag = true;}}if(!flag) return true;}for(int j = 0; j < e.size(); ++j) {memset(vis, 0, sizeof(vis));if(dfs(e[j].v) && dist[e[j].v] > dist[e[j].u] + e[j].cost)return false;}return true;
}int main()
{int kase = 0;int T; scanf("%d", &T);while(T --){e.clear();int n, m;scanf("%d%d", &n, &m);for(int i = 0; i < n; i++)ee[i].clear();while(m --){int u, v, cost;scanf("%d%d%d",&u, &v, &cost);ee[u].push_back(v);e.push_back(Edge(u, v, cost));}printf("Case #%d: %s\n",++kase, !bellman_ford(0, n) ? "possible" : "not possible");}return 0;
}
这篇关于uvalive 6800 - The Mountain of Gold? 判负环的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
