ZOJ 3475 The Great Wall I

最小割建图好题！！

昨天比赛的最小割，当时没看出来，实际上需要建图转化一下，这道题非常显然！！！
比赛后不想看题解，问了一下Yasola，指点了一下马上懂了！！

题意：
有n×m的地图，地图上最多有6个国家，现在K国要修长城，来防御敌对国家，6个国家中除了K国和一个敌对国家，其余国家都是友好国家，想要进供从而使得自己在长城防御范围内。建立长城的每一个花费都已经给出。
问最小花费。

思路：
将地图以外的地方视为敌对，将一个地图上的格子与其上下左右相连。
对于一个长城，实际上就是将K过与友好国家 与 敌对国家割开的最小割。
又因为点数和边数都很少，最多通过枚举 2^5 枚举将友好国家包围的情况，每次求一下最小割即可。

AC Code

#include <bits/stdc++.h>

using namespace std;
const int maxn = 404;
const int maxm = 1e4 + 5;
const int inf = 0x3f3f3f3f;

int n, m, st, en, idx, tidx;
int cur[maxn], level[maxn], head[maxn], thead[maxn];
int cap[maxm];
int afford[10], x[10], y[10];

struct node {
    int to, next;
    int cap;
    node() {}
    node(int _to, int _next, int _cap) { to = _to, next = _next, cap = _cap; }
} edges[maxm << 1];

queue<int> que;

int getNode(int a, int b) { return a * m + b; }

void addEdge(int u, int v, int c)
{
    edges[idx] = node(v, head[u], c);
    head[u] = idx++;
    edges[idx] = node(u, head[v], c);
    head[v] = idx++;
}

bool bfs()
{
    memset(level, -1, sizeof level);
    que.push(st);
    level[st] = 0;
    int u;
    while (!que.empty()) {
        u = que.front();
        que.pop();
        for (int id = head[u]; ~id; id = edges[id].next) {
            int v = edges[id].to;
            if (edges[id].cap > 0 && level[v] == -1) {
                level[v] = level[u] + 1;
                que.push(v);
            }
        }
    }
    return level[en] != -1;
}

int dfs(int u, int low)
{
    int cflow;
    if (u == en)
        return low;
    for (int& id = cur[u]; ~id; id = edges[id].next) {
        int v = edges[id].to;
        if (edges[id].cap > 0 && level[v] == level[u] + 1
            && (cflow = dfs(v, min(low, edges[id].cap)))) {
            edges[id].cap -= cflow;
            edges[id ^ 1].cap += cflow;
            return cflow;
        }
    }
    return 0;
}

int dinic()
{
    int ans = 0, cflow;
    while (bfs()) {
        for (int i = 0; i <= en; i++)
            cur[i] = head[i];
        while ((cflow = dfs(st, inf)))
            ans += cflow;
    }
    return ans;
}

int main()
{
    int c;
    while (scanf("%d %d", &n, &m) != EOF) {
        memset(head, -1, sizeof head), idx = 0;
        st = n * m, en = n * m + 1;
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%d", &c);
                addEdge(i == 0 ? en : getNode(i - 1, j), i == n ? en : getNode(i, j), c);
            }
            if (i == n)
                continue;
            for (int j = 0; j <= m; j++) {
                scanf("%d", &c);
                addEdge(j == 0 ? en : getNode(i, j - 1), j == m ? en : getNode(i, j), c);
            }
        }
        scanf("%d", &c);
        for (int i = 0; i < c; i++) {
            scanf("%d %d %d", afford + i, x + i, y + i);
            if (afford[i] == 0)
                swap(afford[0], afford[i]), swap(x[0], x[i]), swap(y[0], y[i]);
            else if (afford[i] < 0)
                addEdge(getNode(x[i], y[i]), en, inf), c--, i--;
        }
        memcpy(thead, head, sizeof head), tidx = idx;
        for (int i = 0; i < idx; i++)
            cap[i] = edges[i].cap;
        int ans = inf;
        for (int i = 1; i < (1 << c); i += 2) {
            int cost = 0;
            memcpy(head, thead, sizeof thead), idx = tidx;
            for (int i = 0; i < idx; i++)
                edges[i].cap = cap[i];
            for (int j = 0; j < c; j++) {
                if (i & (1 << j)) {
                    cost -= afford[j];
                    addEdge(st, getNode(x[j], y[j]), inf);
                }
            }
            cost += dinic();
            ans = min(ans, cost);
        }
        printf("%d\n", ans);
    }
    return 0;
}