网络流

图论

最大流

一般增广路算法——Ford-Fulkerson（标号法）

复杂度

O(nmU)

Demo

const int inf = 0x3f3f3f3f;
const int maxn = 1010;
struct Edge {
    int c, f;
} edge[maxn][maxn];
int n, m;
int vis[maxn], prev[maxn], alpha[maxn];
void ford() {
    while (1) {
        memset(vis, 0, sizeof(vis));
        vis[0] = 1;
        prev[0] = 0;
        alpha[0] = inf;
        queue <int> q;
        q.push(0);
        while (!q.empty() && !vis[n-1]) {
            int u = q.front();
            q.pop();
            for (int v = 0; v < n; v ++) {
                if (!vis[v]) {
                    if (edge[u][v].c < inf && edge[u][v].f < edge[u][v].c) {//用edge[u][v].c < inf表示u，c之间有边
                        vis[v] = 1;
                        prev[v] = u;
                        alpha[v] = min(alpha[u], edge[u][v].c - edge[u][v].f);
                        q.push(v);
                    } else if (edge[v][u].c < inf && edge[v][u].f > 0) {
                        vis[v] = 1;
                        prev[v] = -u;
                        alpha[v] = min(alpha[u], edge[v][u].f);
                        q.push(v);
                    }
                }
            }
        }
        if (!vis[n-1] || alpha[n-1] == 0) break;
        int k1 = n - 1;
        int k2 = abs(prev[k1]);
        int a = alpha[n-1];
        while (1) {
            if (edge[k2][k1].f < inf) edge[k2][k1].f += a;
            else edge[k1][k2].f -= a;
            if (k2 == 0) break;
            k1 = k2;
            k2 = abs(prev[k1]);
        }
    }
    int max_flow = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (i == 0 && edge[i][j].f < inf) max_flow += edge[i][j].f;
            if (edge[i][j].f < inf) printf("%d->%d : %d\n", i, j, edge[i][j].f);
        }
    }
    printf("max_flow : %d\n", max_flow);
}
int main() {
    int u, v, c, f;
    scanf("%d %d", &n, &m);
    memset(edge, 0x3f, sizeof(edge));
    for (int i = 0; i < m; i ++) {
        scanf("%d %d %d %d", &u, &v, &c, &f);
        edge[u][v].c = c;
        edge[u][v].f = f;
    }
    ford();
    return 0;
}
/*
input:
6 10
0 1 8 2
0 2 4 3
1 3 2 2
1 4 2 2
2 1 4 2
2 3 1 1
2 4 4 0
3 4 6 0
3 5 9 3
4 5 7 2
output:
0->1 : 4
0->2 : 4
1->3 : 2
1->4 : 2
2->1 : 0
2->3 : 1
2->4 : 3
3->4 : 0
3->5 : 3
4->5 : 5
max_flow : 8
*/

例题

POJ 1149 PIGS

题意
迈克在一个养猪场工作，养猪场里有M 个猪圈，每个猪圈都上了锁。由于迈克没有钥匙，所以他不能打开任何一个猪圈。要买猪的顾客一个接一个来到养猪场，每个顾客有一些猪圈的钥匙，而且他们要买一定数量的猪。某一天，所有要到养猪场买猪的顾客，他们的信息是要提前让迈克知道的。这些信息包括：顾客所拥有的钥匙（详细到有几个猪圈的钥匙、有哪几个猪圈的钥匙）、要购买的数量。这样对迈克很有好处，他可以安排销售计划以便卖出的猪的数目最大。
更详细的销售过程：当每个顾客到来时，他将那些他拥有钥匙的猪圈全部打开；迈克从这些猪圈中挑出一些猪卖给他们；如果迈克愿意，迈克可以重新分配这些被打开的猪圈中的猪；当顾客离开时，猪圈再次被锁上。注意：猪圈可容纳的猪的数量没有限制。
求迈克这一天能卖出猪的最大数目。
输入
1) 第一行是两个整数：M 和N（1≤M≤1000，1≤N≤100）。M 是猪圈的数目，N 是顾客的数目。猪圈的编号从1 到M，顾客的编号从1 到N。
2) 第二行是M 个整数，为每个猪圈中初始时猪的数目，范围是[0，1000]。
3) 接下来的N 行是顾客的信息，第i 个顾客的信息保存在第i+2 行。格式为：A K1 K2…KA
B。A 为拥有钥匙的数目，Kj 表示拥有第Kj 个猪圈的钥匙，B 为该顾客想买的猪的数目。
A，B 均可为0。
输出
输出有且仅有一行，为迈克能够卖掉的猪的最大数目。

思路

• 将顾客看作除源点和汇点以外的结点，另设 2 个结点：源点和汇点；
• 源点和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数目；
• 若源点和某个结点之间有重边，则将权合并（因此源点流出的流量就是所有的猪圈能提供的猪的数目）；
• 顾客j 紧跟在顾客i 之后打开某个猪圈，则边的权是+∞；这是因为，如果顾客j 紧跟在顾客i 之后打开某个猪圈，那么迈克就有可能根据顾客j 的需求将其他猪圈中的猪调整到该猪圈，这样顾客j 就能买到尽可能多的猪；
• 每个顾客和汇点之间连边，边的权是顾客所希望购买的猪的数目（因此汇点的流入量就是每个顾客所购买的猪的数目）。

AC代码

const int inf = 0x3f3f3f3f;
const int maxm = 1005;
const int maxn = 1005;//不知道为什么换成105就RE了= =||
int s, t;
int c[maxn][maxn];
int flow[maxn][maxn];
int num[maxm];
int buy[maxn];
int prev[maxn];
int alpha[maxn];
int vis[maxn];
int m, n;
void init() {
    while (~scanf("%d %d", &m, &n)) {//m个猪圈，n位顾客
        memset(c, 0, sizeof(c));
        memset(vis, 0, sizeof(vis));
        s = 0;
        t = n + 1;
        for (int i = 1; i <= m; i ++) scanf("%d", &num[i]);
        for (int i = 1; i <= n; i ++) {
            int key;
            scanf("%d", &key);
            for (int j = 1; j <= key; j ++) {
                int key_id;
                scanf("%d", &key_id);
                if (vis[key_id]) c[vis[key_id]][i] = inf;
                else c[s][i] += num[key_id];
                vis[key_id] = i;
            }
            scanf("%d", &c[i][t]);
        }
    }
}
void ford() {
    memset(flow, 0, sizeof(flow));
    while (1) {
        memset(vis, 0, sizeof(vis));
        vis[s] = 1;
        prev[s] = s;
        alpha[s] = inf;
        queue <int> q;
        q.push(s);
        while (!q.empty() && !vis[t]) {
            int u = q.front();
            q.pop();
            for (int v = s; v <= t; v ++) {
                if (!vis[v]) {
                    if (c[u][v] && flow[u][v] < c[u][v]) {
                        vis[v] = 1;
                        prev[v] = u;
                        alpha[v] = min(alpha[u], c[u][v] - flow[u][v]);
                        q.push(v);
                    } else if (c[v][u] && flow[v][u] > 0) {
                        vis[v] = 1;
                        prev[v] = -u;
                        alpha[v] = min(alpha[u], flow[v][u]);
                        q.push(v);
                    }
                }
            }
        }
        if (!vis[t] || alpha[t] == 0) break;
        int k1 = t;
        int k2 = abs(prev[k1]);
        int a = alpha[t];
        while (1) {
            if (c[k2][k1]) flow[k2][k1] += a;
            else flow[k1][k2] -= a;
            if (k2 == 0) break;
            k1 = k2;
            k2 = abs(prev[k1]);
        }
    }
    int max_flow = 0;
    for (int i = 1; i <= n; i ++) {
        if (flow[s][i]) max_flow += flow[s][i];
    }
    printf("%d\n", max_flow);
}
int main() {
    init();
    ford();
    return 0;
}