2分法,对于最后能否达到x应满足每一对的:
edge(u, v) + sum(u) - sum(v) >= x
-->sum(v) <= sum(u) + (edge(u, v) - x)
-->d[v] <= d[u] + edge0(u, v)
-->模拟建图,判断是否有负环
注意:题目的目标是所有边的权值都大于0而不是非负
#include <stdio.h> #include <string.h> #include <algorithm> #include <vector> #include <queue> using namespace std; const int maxn = 500+5; class Edge { public: int pos, dist; Edge(int pos, int dist) { this->pos = pos; this->dist = dist; } }; vector<Edge> adj[maxn]; bool inq[maxn]; int d[maxn], cnt[maxn], n, m, up; void Init() { for(int i = 1; i <= n; i++) adj[i].clear(); int a, b, c; up = 0; for(int i = 1; i <= m; i++) { scanf("%d%d%d", &a, &b, &c); adj[a].push_back(Edge(b, c)); up = max(up, c); } } bool Bellman_Ford() { queue<int> myQue; for(int i = 1; i <= n; i++) { myQue.push(i); inq[i] = true; d[i] = 0; cnt[i] = 0; } while(!myQue.empty()) { int u = myQue.front(); myQue.pop(); inq[u] = false; for(vector<Edge>::iterator it = adj[u].begin(); it != adj[u].end(); it++) { int v = it->pos; if(d[v] > d[u] + it->dist) { d[v] = d[u] + it->dist; if(!inq[v]) { myQue.push(v); inq[v] = true; if(++cnt[v] > n) return true;//有负环 } } } } return false; } bool Test(int M) { for(int i = 1; i <= n; i++) for(vector<Edge>::iterator it = adj[i].begin(); it != adj[i].end(); it++) it->dist -= M; bool flag = Bellman_Ford(); for(int i = 1; i <= n; i++) for(vector<Edge>::iterator it = adj[i].begin(); it != adj[i].end(); it++) it->dist += M; return flag; } void Solve() { if(!Test(up+1)) printf("Infinite\n"); else if(Test(1)) printf("No Solution\n"); else { int L = 1, R = up + 1; while(L < R - 1) { int M = L + (R - L) / 2; if(!Test(M)) L = M; else R = M; } printf("%d\n", L); } } int main() { while(scanf("%d%d", &n, &m) != EOF) { Init(); Solve(); } return 0; }