一些经典题目
找可达路径
UVa - 11604 General Sultan
平面图最小割=对偶图最短路
UVa - 1376 Animal Run
最小割建模
UVa - 1515 Pool construction
费用流建模
洛谷P3159 [CQOI2012] 交换棋子
一些可以转化为二分图最大权匹配的建模题
UVa1006/LA2238 Fixed Partition Memory Management
洛谷P2053 [SCOI2007] 修车
跑费用流的过程中动态加点连边的好题
洛谷P2050 [NOI2012] 美食节
这道题目是洛谷P2053 [SCOI2007] 修车的加强版，数据量变大 ( n ≤ 40 ， m ≤ 100 ， P ≤ 800 ， t i , j ≤ 1000 ，其中 P = ∑ p i ) (n≤40，m≤100，P≤800，t_{i,j}≤1000，其中P=∑p_i) (n≤40，m≤100，P≤800，ti,j≤1000，其中P=∑pi)，如果继续用KM算法求二分图最大权匹配的话，点数的规模是 𝑂(𝑚𝑃 + 𝑃)，边数的规模是 𝑂(𝑃𝑚𝑃)，会超时。
如果直接用费用流求解，则点数的规模是𝑂(𝑚𝑃 + 𝑛)，边数的规模是 𝑂(𝑛𝑚𝑃)，也会超时。要想办法去掉冗余的点和边（每个厨师不会都要做𝑃道菜）。由于费用流算法每次只能找出一条增广路，所以可以先不连不需要的边。一开始，把所有厨师做倒数第１道菜与所有菜连好，然后找一条增广路，表示第j个厨师做倒数第１道菜，然后继续添加点（第j个厨师做倒数第２道菜），与汇点和所有菜连边，以此类推。
#include <iostream>
#include <cstring>
using namespace std;#define INF 900000
#define N 42
#define M 102
#define P 1002
struct edge {int u, v, cap, flow, cost, c;} e[N*P<<1];
int g[P][P], x[N][M], y[M], q[N*P*P<<1], a[P], d[P], p[P], cnt[P], c, m, n; bool vis[P];void add_edge(int u, int v, int cap, int cc) {e[c].u = u; e[c].v = v; e[c].cap = cap; e[c].flow = 0; e[c].cost = cc; g[u][cnt[u]++] = c++;e[c].u = v; e[c].v = u; e[c].cap = 0; e[c].flow = 0; e[c].cost = -cc; g[v][cnt[v]++] = c++;
}int solve() {memset(cnt, c = 0, sizeof(cnt));int s = 0, t = n+1, b = t, f, cc = 0;for (int i=1, c; i<=n; ++i) cin >> c, add_edge(0, i, c, 0);for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j)cin >> x[i][j], add_edge(i, b+j, 1, x[i][j]);for (int i=1; i<=m; ++i) y[i] = 1, e[c].c = i, add_edge(++b, t, 1, 0);while (true) {memset(d, 1, sizeof(d)); memset(vis, 0, sizeof(vis));d[s] = 0; q[0] = s; a[s] = INF;int head = 0, tail = 1;while (head < tail) {short u = q[head++]; vis[u] = false;for (short i=0; i<cnt[u]; ++i) {const edge& ee = e[g[u][i]];if (ee.cap > ee.flow && d[ee.v] > d[u]+ee.cost) {d[ee.v] = d[u]+ee.cost;p[ee.v] = g[u][i];a[ee.v] = min(a[u], ee.cap-ee.flow);if (!vis[ee.v]) vis[q[tail++] = ee.v] = true;}}}if (d[t] >= INF) return cc;cc += d[t];for (short u=t; u!=s; u=e[p[u]].u) {e[p[u]].flow += a[t], e[p[u]^1].flow -= a[t];if (e[p[u]].v == t && e[p[u]].flow) f = e[p[u]].c;}++y[f]; e[c].c = f; add_edge(++b, t, 1, 0);for (int i=1; i<=n; ++i) add_edge(i, b, 1, y[f]*x[i][f]);}return cc;
}int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);while (cin >> n >> m) cout << solve() << endl;return 0;
}
其他人写的博客
最详细（也可能现在不是了）网络流建模基础
最小割模型
洛谷 网络流24题
