http://poj.org/problem?id=2175
题意：有n个楼，m个防空洞，每个楼有一个坐标和一个人数B，每个防空洞有一个坐标和容纳量C，从楼到防空洞需要的时间是其曼哈顿距离+1，现在给出一个方案，问该方案是否是让所有人到防空洞避难的花费时间最少的方案，如果不是，输出一个最佳方案。
思路：一开始直接用最小费用最大流，超时了。学习了一下消圈算法。
如果不考虑得到最小费用，只需要考虑当前是否最小费用的话，那么是可以用消圈算法来解决的。
结论：当没有负圈的时候，当前的费用是最小的。
因此，构图的时候，根据给出的方案构造出残余网络，然后直接跑一遍SPFA，如果出现负圈，说明当前的答案不是最优的（因为反向边是-cost，可以得到更小的费用，因此是负圈）。
考虑构造新的方案：对于该负圈，记录起路径，然后遍历，因为图存的是正向边的流量，所以如果正向边出现在负圈里，需要加上，代表跑这条边更优,反向边则减去。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <stack> 12 using namespace std; 13 #define INF 0x3f3f3f3f 14 #define N 210 15 typedef long long LL; 16 struct Edge { 17 int u, v, nxt, cap, cost; 18 } edge[N*N]; 19 int head[N], tot, pre[N], dis[N], vis[N], inq[N], x[N], y[N], b[N], p[N], q[N], c[N], mp[N][N], S, T; 20 21 void Add(int u, int v, int cap, int now, int cost) { 22 edge[tot] = (Edge) { u, v, head[u], cap - now, cost }; head[u] = tot++; 23 edge[tot] = (Edge) { v, u, head[v], now, -cost }; head[v] = tot++; 24 } 25 26 int cal(int x1, int y1, int x2, int y2) { return abs(x2 - x1) + abs(y2 - y1) + 1; } 27 28 int SPFA(int S, int n) { 29 queue<int> que; 30 que.push(S); 31 memset(dis, INF, sizeof(dis)); 32 memset(vis, 0, sizeof(vis)); 33 memset(inq, 0, sizeof(inq)); 34 dis[S] = 0; vis[S] = 1; pre[S] = S; 35 while(!que.empty()) { 36 int u = que.front(); que.pop(); 37 vis[u] = 0; 38 for(int i = head[u]; ~i; i = edge[i].nxt) { 39 int v = edge[i].v, cost = edge[i].cost, cap = edge[i].cap; 40 if(dis[v] > dis[u] + cost && cap > 0) { 41 dis[v] = dis[u] + cost; pre[v] = u; 42 if(!vis[v]) { 43 vis[v] = 1, que.push(v); 44 if(++inq[v] > n) return v; 45 } 46 } 47 } 48 } 49 return 0; 50 } 51 52 bool inside(int L, int R, int now) { if(L <= now && now <= R) return true; return false; } 53 54 int main() { 55 int n, m; 56 while(~scanf("%d%d", &n, &m)) { 57 S = 0, T = n + m + 1; int res = 0, ans; 58 memset(head, -1, sizeof(head)), tot = 0; 59 memset(dis, 0, sizeof(dis)); 60 for(int i = 1; i <= n; i++) scanf("%d%d%d", &x[i], &y[i], &b[i]); 61 for(int i = 1; i <= m; i++) scanf("%d%d%d", &p[i], &q[i], &c[i]); 62 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { 63 scanf("%d", &mp[i][j]); 64 int d = cal(x[i], y[i], p[j], q[j]); 65 Add(i, j + n, INF, mp[i][j], d); 66 res += d * mp[i][j]; dis[j] += mp[i][j]; 67 } 68 for(int i = 1; i <= n; i++) Add(S, i, b[i], 0, 0); 69 for(int i = 1; i <= m; i++) Add(i + n, T, c[i], dis[i], 0); 70 ans = SPFA(S, T); 71 if(!ans) puts("OPTIMAL"); 72 else { 73 memset(vis, 0, sizeof(vis)); 74 while(!vis[ans]) { vis[ans] = 1; ans = pre[ans]; } 75 int tmp = ans; 76 do { // 图存的是正向边的流量,因此如果正向边出现在负圈里,需要加上,代表跑这条边更优,反向边减去 77 if(inside(1, n, pre[tmp]) && inside(n + 1, n + m, tmp)) mp[pre[tmp]][tmp-n]++; 78 if(inside(1, n, tmp) && inside(n + 1, n + m, pre[tmp])) mp[tmp][pre[tmp]-n]--; 79 tmp = pre[tmp]; 80 } while(tmp != ans); 81 puts("SUBOPTIMAL"); 82 for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) 83 printf("%d%c", mp[i][j], j == m ? '\n' : ' '); 84 } 85 } 86 return 0; 87 } 88 89 /* 90 3 4 91 -3 3 5 92 -2 -2 6 93 2 2 5 94 -1 1 3 95 1 1 4 96 -2 -2 7 97 0 -1 3 98 3 1 1 0 99 0 0 6 0 100 0 3 0 2 101 */