 |
6800 - The Mountain of Gold? |
题目大意：
给定一张有向图，问能否从0号点出发，回到0号点，经过的路径上边权之和小于0。若可能，输出“possible”，否则输出“not possible”。
解题思路：
Bellman Ford算法不但可以计算单源最短路径，还可以应用于判断：从源点出发，是否能够到达一个负环。
应用于本题，因为只要从0出发，能够到达一个负环，并且还能走回的话，就能实现要求（负环外的边权不用考虑，在负环内多走几圈，肯定能使总边权小于0）。所以用Bellman Ford找出所有从0出发能到达的负环，再用记忆化搜索的方法，判断负环上的任意一点，是否与0相连。一个点能与0相连，那么与这个点相连的点，也能与0相连（注意是有向边）
参考代码：
#include#include #include #include using namespace std; const int MAXN = 1010; const int MAXM = 2010; const int INF = 0x3f3f3f3f; struct Edge { int u, v, cost; } edge[MAXM]; int nCase, cCase, n, m, dis[MAXN]; bool visited[MAXN], dp[MAXN]; vector G[MAXN]; bool dfs(int n) { if (n == 0) return true; if (visited[n]) return dp[n]; visited[n] = true; for (int i = 0; i < G[n].size(); i++) { if (dfs(G[n][i])) { return dp[n] = true; } } return dp[n] = false; } bool Bellman_Ford() { for (int i = 0; i < n; i++) { dis[i] = (i == 0 ? 0 : INF); } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < m; j++) { if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) { dis[edge[j].v] = dis[edge[j].u] + edge[j].cost; } } } for (int i = 0; i < m; i++) { if (dis[edge[i].v] > dis[edge[i].u] + edge[i].cost) { if (dfs(edge[i].u)) return false; } } return true; } void init() { memset(visited, false, sizeof(visited)); memset(dp, false, sizeof(dp)); dp[0] = visited[0] = true; for (int i = 0; i < MAXN; i++) { G[i].clear(); } } void input() { scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost); G[edge[i].u].push_back(edge[i].v); } } void solve() { if (!Bellman_Ford()) { printf("Case #%d: possible\n", ++cCase); } else { printf("Case #%d: not possible\n", ++cCase); } } int main() { scanf("%d", &nCase); while (nCase--) { init(); input(); solve(); } return 0; }