POJ 2175 Evacuation Plan 費用流消圈

題目：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;
}