POJ No 3259 Wormholes Bellman-Ford 判断是否存在负图
题目：http://poj.org/problem?id=3259
题意：主要就是构造图， 然后判断，是否存在负图，可以回到原点
/*
2
3 3 1 //N, M, W1 2 2
1 3 4
2 3 13 1 3 //虫洞 3 2 1 //N, M, W1 2 3
2 3 43 1 8*/
#include <iostream>
#include <cstring>
using namespace std;const int maxn = (2500 + 200 + 16) * 2 + 24;
const int INF = 10000 + 10;
int N, M, W;//(from, to) 权值为cost
struct Edge {int from,to, cost;Edge(int f = 0, int t = 0, int c = 0) :from(f), to(t), cost(c) {}
};//边
Edge es[maxn];int d[maxn]; //最短距离
int V, E; //顶点数，E边数 bool find_negative_loop()
{memset(d, 0, sizeof(d));for (int i = 0; i < V; i++) {for (int j = 0; j < E; j++) {Edge e = es[j];if (d[e.to] > d[e.from] + e.cost) {d[e.to] = d[e.from] + e.cost;//如果第n次仍然更新了，则存在负圈if (i == V - 1) return true; }}}return false;
}void solve()
{int F;int from, to, cost;scanf("%d", &F);while (F--){scanf("%d%d%d", &N, &M, &W); //顶点数，边数, 虫洞数 V = N; E = 0; // E = M * 2 应该 for (int i = 0; i < M; ++i) {cin >> from >> to >> cost;--from; --to; //无向图 -- 去 es[E].from = from; es[E].to = to;es[E].cost = cost; ++E; //回 -- 再来一次 es[E].from = to; es[E].to = from;es[E].cost = cost; ++E;}for (int i = 0; i < W; i++){cin >> from >> to >> cost;--from; --to; es[E].from = from;es[E].to = to;//虫洞 - 回路 es[E].cost = -cost;++E; }if (find_negative_loop()) {printf("YES\n");} else {printf("NO\n");}}
}int main()
{solve();return 0;}
posted @ 2017-05-18 01:10 douzujun 阅读(...) 评论(...) 编辑 收藏