POJ_2175
据说这个题目裸着做费用流会超时，不过实际上看完这个题目还是不难发现更好的思路的，因为题目又没要求要最优解，而是得到一个更优的解，那么如果在原图中能够找到一个总费用为负的回路的话，那么沿这个回路流量增加1就能够在不改变原始总流量的基础上使总费用变得更低，于是我们只要试图去找这样一个负圈就可以了。
如果用的SPFA的话，在一个点入队次数大于顶点数时就可以判断有负圈存在了，但这时刚刚入队的这个点却未必是负圈上的，但我们可以记录下来每个点被更新的前一个点，沿这个路径不停地回溯去找，直到发现找到的这个点在之间已经遇到过了，那么找到的这个点就一定是某个负圈上的点了。最后以这个点为基础，回溯找到整个负圈并更新流量即可。
如果用Bellman-Ford的话，找负圈上的点就要更加纠结一些了……
#include<stdio.h> #include<string.h> #include<stdlib.h> #define MAXD 210 #define MAXM 20410 #define INF 0x3f3f3f3f int N, M, first[MAXD], e, next[MAXM], v[MAXM], flow[MAXM], cost[MAXM]; int dis[MAXD], pre[MAXD], vis[MAXD], sum[MAXD]; struct Point { int x, y, z; }p[MAXD]; int Dis(int i, int j) { return abs(p[i].x - p[j].x) + abs(p[i].y - p[j].y) + 1; } void add(int x, int y, int f, int c) { v[e] = y, flow[e] = f, cost[e] = c; next[e] = first[x], first[x] = e ++; } void init() { int i, j, x, y, z; memset(first, -1, sizeof(first[0]) * (N + M + 1)), e = 0; for(i = 0; i < N + M; i ++) scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].z); memset(sum, 0, sizeof(sum[0]) * M); for(i = 0; i < N; i ++) for(j = 0; j < M; j ++) { scanf("%d", &x), sum[j] += x; add(i, N + j, INF - x, Dis(i, N + j)), add(N + j, i, x, -Dis(i, N + j)); } for(i = 0; i < M; i ++) add(N + i, N + M, p[N + i].z - sum[i], 0), add(N + M, N + i, sum[i], 0); } int dfs(int cur, int &x) { int i = pre[cur]; if(i == -1 || vis[cur] == 1) return 0; if(vis[cur] == -1) { x = cur; return 1; } vis[cur] = -1; if(dfs(v[i ^ 1], x)) return 1; vis[cur] = 1; return 0; } void print() { int i, j, x; memset(vis, 0, sizeof(vis[0]) * (N + M + 1)); for(i = 0; i <= N + M; i ++) if(!vis[i] && dfs(i, x)) break; for(i = pre[x]; ; i = pre[v[i ^ 1]]) { flow[i] -= 1, flow[i ^ 1] += 1; if(v[i ^ 1] == x) break; } printf("SUBOPTIMAL\n"); for(i = 0; i < N; i ++) { printf("%d", flow[i * M * 2 + 1]); for(j = 1; j < M; j ++) printf(" %d", flow[(i * M + j) * 2 + 1]); printf("\n"); } } void solve() { int i, j, flag; memset(dis, 0, sizeof(dis[0]) * (N + M + 1)); memset(pre, -1, sizeof(pre[0]) * (N + M + 1)); for(i = 0; i <= N + M; i ++) { flag = 0; for(j = 0; j < e; j ++) if(flow[j] && dis[v[j]] > dis[v[j ^ 1]] + cost[j]) dis[v[j]] = dis[v[j ^ 1]] + cost[j], pre[v[j]] = j, flag = 1; if(flag == 0) break; } if(i > N + M) print(); else printf("OPTIMAL\n"); } int main() { while(scanf("%d%d", &N, &M) == 2) { init(); solve(); } return 0; }