题目：http://poj.org/problem?id=2175
题意：有n个建筑和m个防空洞，每个建筑里初始有一定数量的人，而防空洞有容量上限，现在让所有在建筑里的人转移到防空洞，从建筑跑到防空洞的花费为他们的曼哈顿距离，现在给出一种转移方案，问是不是最小花费，若不是，给出一种更小的花费（不需要是最小花费，比给定的小即可）
思路：第一次接触到费用流消圈。在本题中，用题目给定的方案构建出残余网络，然后以汇点为起点跑spfa，检查有没有负环，如果有负环，那么沿着负环走一次可以使花费更小，于是我们把在负环上的正费用边流量加1，负费用边流量减1，可以得出花费更小的方案。更具体的可以看这篇博客：http://blog.csdn.net/u013761036/article/details/46363631
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
using namespace std;
const int N = 300;
const int INF = 0x3f3f3f3f;
struct edge
{
int st, to, cap, cost, next;
}g[N*N];
int que[N*N*2];
struct node
{
int x, y, c;
}arr[N], brr[N];
int cnt, head[N];
int dis[N], pre[N], mark[N], s[N][N], sum[N];
int mpa[N][N];
bool vis[N];
int n, m;
void add_edge(int v, int u, int cap, int cost)
{
g[cnt].st = v, g[cnt].to = u, g[cnt].cap = cap, g[cnt].cost = cost, g[cnt].next = head[v], head[v] = cnt++;
}
int spfa(int s, int n)
{
memset(dis, 0x3f, sizeof dis);
memset(pre, -1, sizeof pre);
memset(vis, 0, sizeof vis);
memset(mark, 0, sizeof mark);
int tip = 0, til = 0;
que[til++] = s;
dis[s] = 0, mark[s]++, vis[s] = true;
while(tip < til)
{
int v = que[tip++];
vis[v] = false;
for(int i = head[v]; i != -1; i = g[i].next)
{
int u = g[i].to;
if(g[i].cap > 0 && dis[u] > dis[v] + g[i].cost)
{
dis[u] = dis[v] + g[i].cost;
pre[u] = i;
if(! vis[u])
{
que[til++] = u, vis[u] = true;
if(++mark[u] > n) return u;
}
}
}
}
return 0;
}
int scan() //输入外挂
{
int flag = 1, res = 0;
char ch;
if((ch = getchar()) == '-') flag = 0;
else if(ch >= '0' && ch <= '9') res = ch - '0';
while((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + ch - '0';
return flag ? res : -res;
}
void out(int a) //输出外挂
{
if(a > 9) out(a / 10);
putchar(a % 10 + '0');
}
int main()
{
while(~ scanf("%d%d", &n, &m))
{
getchar();
cnt = 0;
memset(head, -1, sizeof head);
for(int i = 1; i <= n; i++)
{
arr[i].x = scan();
arr[i].y = scan();
arr[i].c = scan();
}
for(int i = 1; i <= m; i++)
{
brr[i].x = scan();
brr[i].y = scan();
brr[i].c = scan();
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
mpa[i][j] = abs(arr[i].x - brr[j].x) + abs(arr[i].y - brr[j].y) + 1;
memset(sum, 0, sizeof sum);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
s[i][j] = scan();
add_edge(i, n + j, INF - s[i][j], mpa[i][j]);
add_edge(n + j, i, s[i][j], -mpa[i][j]);
sum[j] += s[i][j];
}
for(int i = 1; i <= n; i++)
add_edge(0, i, 0, 0), add_edge(i, 0, arr[i].c, 0);
for(int i = 1; i <= m; i++)
add_edge(n + i, n + m + 1, brr[i].c - sum[i], 0), add_edge(n + m + 1, n + i, sum[i], 0);
int r = spfa(n + m + 1, n + m + 1);
if(! r) puts("OPTIMAL");
else
{
puts("SUBOPTIMAL");
memset(vis, 0, sizeof vis);
while(!vis[r]) //找出第一个在负环上的点
{
vis[r] = true;
r = g[pre[r]].st;
}
memset(vis, 0, sizeof vis);
for(int i = pre[r]; i != -1; i = pre[g[i].st])
{
int a = g[i].st, b = g[i].to;
if(a <= n && b > n) s[a][b-n]++;
if(b <= n && a > n) s[b][a-n]--;
if(vis[a] && vis[b]) break;
vis[a] = vis[b] = true;
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
{
out(s[i][j]);
putchar(j == m ? '\n' : ' ');
}
}
}
return 0;
}