最小割

一个图，每条边都有一个代价，现在需要破坏一些边使图中的某两个点不连通，求最小的代价是多少。
根据最大流-最小割定理，最小割可以通过最大流来求。
最小割的模板同最大流 如果只要求割成两部分，并不在意隔开了哪些点，这是全图最小割问题，可以供SW算法，模板如下:

HDU 3691 Nubulsa Expo

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))

const int maxv = 500;
const int inf = 0x3f3f3f3f;

int v[maxv], d[maxv];
int G[maxv][maxv];
bool vis[maxv];

int Stoer_Wanger(int n) {
    int res = inf;
    for (int i = 1; i <= n; i++) v[i] = i;

    while (n > 1) {
        int k = 1, pre = 1;
        mem(vis); mem(d);
        for (int i = 2; i <= n; i++) {
            k = -1;
            for (int j = 2; j <= n; j++) {
                if ( !vis[ v[j] ] ) {
                    d[ v[j] ] += G[ v[pre] ][ v[j] ];
                    if (k == -1 || d[ v[k] ] < d[ v[j] ] ) {
                        k = j;
                    }
                }
            }
            vis[ v[k] ] = true;
            if (i == n) {
                res = min(res, d[ v[k] ]);
                for (int j = 1; j <= n; j++) {
                    G[ v[pre] ][ v[j] ] += G[ v[j] ][ v[k] ];
                    G[ v[j] ][ v[pre] ] += G[ v[j] ][ v[k] ];
                }
                v[ k ] = v[ n-- ];
            }
            pre = k;
        }
    }
    return res;
}

int main() {
    int n, m, s, u, v, w;
    while (scanf("%d%d%d", &n, &m, &s) != EOF && s) {
        mem(G);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            G[u][v] += w;
            G[v][u] += w;
        }
        printf("%d\n", Stoer_Wanger(n));
    }
    return 0;
}

POJ 3469 Dual Core CPU

有一台电脑配了一个双核的CPU，现在内存中有N个模块，每个模块在每个CPU中运行的耗费已经被估算出来了，设为Ai 和Bi。同时，其中有M对模块需要共享资源，如果他们运行在同一个CPU中，共享数据的耗费可以忽略不计，否则，还需要额外的费用。必须很好的安排这N个模块，使得总耗费最小。

如果将两个CPU分别视为源点和汇点、模块视为顶点，则可以按照以下方式构图： 对于第 i 个模块在每个CPU中的耗费Ai,Bi,从源点向顶点 i 连接一条容量为 w 的弧、从顶点 i 向汇点连接一条容量为Bi的弧；对于a 模块与 b 模块在不同的CPU中运行造成的额外耗费w，从顶点a 向顶点 b连接一条容量为 w 的弧。此时每个顶点（模块）都和源点及汇点（两个CPU）相连，即每个模块都可以在任意一个CPU中运行。

不难发现，对于图中的任意一个割，源点与汇点必不连通。因此每个顶点（模块）都不可能同时和源点及汇点（两个CPU）相连，即每个模块只能在同一个CPU中运行。此时耗费即为割的容量。显然，当割的容量最小时，总耗费最小。故题目转化为求最小割的容量

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 100000;
const int maxm = 1000000;
const int inf = 1000000000;

class Dinic {
public :
    struct Node {
        int u, v, f, next;
    }e[maxm];

    int head[maxn], p, lev[maxn], cur[maxn];
    int que[maxm];

    void init() {
        p = 0;
        memset(head, -1, sizeof(head));
    }

    void add(int u, int v, int f) {
        e[p].u = u; e[p].v = v; e[p].f = f; e[p].next = head[u]; head[u] = p++;
        e[p].u = v; e[p].v = u; e[p].f = 0; e[p].next = head[v]; head[v] = p++;
    }

    bool bfs(int s, int t) {
        int u, v, qin = 0, qout = 0;
        memset(lev, 0, sizeof(lev)); lev[s] = 1; que[qin++] = s;
        while(qout != qin) {
            u = que[qout++];
            for(int i = head[u]; i != -1; i = e[i].next) {
                if(e[i].f > 0 && !lev[v = e[i].v]) {
                    lev[v] = lev[u] + 1, que[qin++] = v;
                    if(v == t) return 1;
                }
            }
        }
        return 0;
    }

    int dfs(int s, int t) {
        int i, f, qin, u, k;
        int flow = 0;
        while(bfs(s, t)) {
            memcpy(cur, head, sizeof(head));
            u = s, qin = 0;
            while(1) {
                if(u == t) {
                    for(k = 0, f = inf; k < qin; k++)
                        if(e[que[k]].f < f) f = e[que[i=k]].f;
                    for(k = 0; k < qin; k++)
                        e[que[k]].f -= f, e[que[k]^1].f += f;
                    flow += f, u = e[que[qin = i]].u;
                }
                for(i = cur[u]; cur[u] != -1; i = cur[u] = e[cur[u]].next)
                    if(e[i].f > 0 && lev[u] + 1 == lev[e[i].v]) break;
                if(cur[u] != -1)
                    que[qin++] = cur[u], u = e[cur[u]].v;
                else {
                    if(qin == 0) break;
                    lev[u] = -1, u = e[que[--qin]].u;
                }
            }
        }
        return flow;
    }
}H;

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        int s = 0, t = n+1;
        H.init();
        int cpu1, cpu2;
        for (int i = 1; i <= n; i++) {
            scanf("%d%d", &cpu1, &cpu2);
            H.add(s, i, cpu1);
            H.add(i, t, cpu2);
        }
        int u, v, w;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d", &u, &v, &w);
            H.add(u, v, w);
            H.add(v, u, w);
        }
        printf("%d\n", H.dfs(s, t));
    }
    return 0;
}