首先，二分图的问题都可以用网络流的相关知识解决，但是匈牙利算法也有不错的效果。
二分图相关概念：
（1）最大匹配数：用匈牙利算法可求得。
（2）最小点覆盖=最大匹配
（3）最小边覆盖=最大独立集=总节点数-最大匹配
如果用网络流的相关知识的话，匈牙利算法的最大匹配，其实就是网络流中的最大流。简单的说，直接建超级源点和超级汇点，然后按原图建边跑最大流就行了。
匈牙利部分：
1.【线性规划与网络流24题#24】骑士共存
solution：二分图板题，即求最大独立集，除了障碍其他的点与自己能够到达的点连边，跑最大匹配即可，最后用总格子数减去障碍数再减去最大匹配的一半即可。
solution：暂时鸽了，贴个码，考察算法：二分图 + 最短路 + 二分。
#include <bits/stdc++.h> using namespace std; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; typedef pair <int, int> P; struct battle { int x, y; }st[100005], des[2000005]; int m, n, k, t, ct, cnt, vis[505][505], cost[505][505], lk[500005], vvis[500005], dis[505][505], h[505][505]; bool check(int x, int y) {return x >= 1 && x <= m && y >= 1 && y <= n;} bool spfa(int s, int p) { queue <P> Q; memset(dis, 0x3f, sizeof dis), memset(vis, 0, sizeof vis); dis[st[s].x][st[s].y] = 0; Q.push(make_pair(st[s].x, st[s].y)); while (!Q.empty()) { int x = Q.front().first, y = Q.front().second; Q.pop(); vis[x][y] = 0; for (int i = 0; i < 4; i++) { int fx = x + dx[i], fy = y + dy[i], l = (p ^ (dis[x][y] & 1) ? h[x][y] < h[fx][fy] : h[x][y] > h[fx][fy]); if (check(fx, fy)) { if (dis[fx][fy] > dis[x][y] + l) { dis[fx][fy] = dis[x][y] + l; if (!vis[fx][fy]) vis[fx][fy] = 1, Q.push(make_pair(fx, fy)); } } } } for (int i = 1; i <= (k << 1 | 1); i++) cost[s][i] = dis[des[i].x][des[i].y]; } bool find(int u, int lim) { for (int v = 1; v <= 2 * k + 1; v++) { if ((vvis[v] ^ cnt) && cost[u][v] <= lim) { vvis[v] = cnt; if (!lk[v] || find(lk[v], lim)) return lk[v] = u, 1; } } return 0; } bool check(int lim) { memset(vvis, 0, sizeof vvis), cnt = 0; memset(lk, 0, sizeof lk); int ans = 0; for (int i = 1; i <= (k << 1); i++) ++cnt, ans += find(i, lim); return ans + lim >= 2 * k; } int main() { scanf("%d%d%d%d", &m, &n, &k, &t); for (int i = 1; i <= (k << 1 | 1); i++) scanf("%d%d", &st[i].x, &st[i].y); for (int i = 1, z; i <= t; i++) { scanf("%d%d%d", &des[i].x, &des[i].y, &z); --z; while (z--) ++ct, des[t + ct] = des[i]; } for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) scanf("%d", &h[i][j]); for (int i = 1; i <= (k << 1); i++) { spfa(i, i > k); } int l = 0, r = 2 * k, mid, ans = 0; while (l <= r) { if (check(mid = l + r >> 1)) r = mid - 1, ans = mid; else l = mid + 1; } printf("%d", ans); }
3.[HNOI2013 DAY1]消毒
solution：暴力枚举最小一维的状态，将其强行转化为二维，于是转化为行列问题，可以用二分图解决。
#include <bits/stdc++.h> using namespace std; int x[500005], y[500005], z[500005], vis[500005], cnt; int a, b, c, ok[500005]; struct node { int to, nxt; }e[2000005]; int head[1000005], tot, lk[500005]; inline void add_e(int u, int v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot;} bool find(int u) {for (int i = head[u], v; i; i = e[i].nxt) if ((v = e[i].to) && (vis[v] ^ cnt) && (vis[v] = cnt) && (!lk[v] || find(lk[v])) && (lk[v] = u)) return 1; return 0;} void solve() { int minn = 0x3f3f3f3f, ans = 0x3f3f3f3f, ct = 0; scanf("%d%d%d", &a, &b, &c); minn = min(a, min(b, c)); for (int i = 1; i <= a; i++) for (int j = 1; j <= b; j++) for (int k = 1, mm; k <= c; k++) { scanf("%d", &mm); if (!mm) continue; x[++ct] = i, y[ct] = j, z[ct] = k; } if (minn == b) swap(a, b), swap(x, y); if (minn == c) swap(a, c), swap(x, z); int all = (1 << a) - 1; for (int s = 0; s <= all; s++) { tot = 0, cnt = 0; int cost = 0; for (int i = 1; i <= b; i++) head[i] = vis[i] = lk[i] = 0; for (int i = 1; i <= a; i++) { if ((1 << (i - 1)) & s) ok[i] = 0, ++cost; else ok[i] = 1; } for (int i = 1; i <= ct; i++) { if (ok[x[i]]) add_e(y[i], z[i]); } for (int i = 1; i <= b; i++) ++cnt, cost += find(i); ans = min(ans, cost); } printf("%d\n", ans); } int main() { int t; scanf("%d", &t); while (t--) solve(); return 0; }
网络流部分：
何老板讲过：所有的图论题其实难点都在于建模，即将复杂的条件转化为一个模型，然后跑经典的图论算法就行了。所以网络流部分，我会着重讲建模的过程。
4.[NOIP 2008]传纸条
问题描述
小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。
一次素质拓展活动中，班上同学安排做成一个m行n列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1)，小轩坐在矩阵的右下角，坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递，从小轩传给小渊的纸条只可以向上或者向左传递。 在活动进行中，小渊希望给小轩传递一张纸条，同时希望小轩给他回复。班里每个同学都可以帮他们传递，但只会帮他们一次，也就是说如果此人在小渊递给小轩纸条的时候帮忙，那么在小轩递给小渊的时候就不会再帮忙。反之亦然。
还有一件事情需要注意，全班每个同学愿意帮忙的好感度有高有低（注意：小渊和小轩的好心程度没有定义，输入时用0表示），可以用一个0-100的自然数来表示，数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条，即找到来回两条传递路径，使得这两条路径上同学的好心程度只和最大。
现在，请你帮助小渊和小轩找到这样的两条路径。
输入格式
第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1≤m,n≤50） 接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的好心程度。每行的n个整数之间用空格隔开。
输出格式
共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的好心程度之和的最大值
思路：也是一道很经典的题了。我记得当初学dp的时候就把这道题当成一道入门题。但是这道题我们同样可以用费用流来解决。并且网络流还可以进一步将这个题推广。
建模过程：将m*n的方阵每一个方块当做一个点。设置超级源点S和超级汇点T，S向(1,1)连边（2,0）（即流量为2，费用为0），(m,n)'向T连边（inf,0）。对于一个点u'，向它右下的的点连边（1,0），对于一个点u，u向u'连边（1,cst），然后跑最大费用最大流即可。
#include <bits/stdc++.h> using namespace std; struct node { int to, nxt, len, fl, cost; }e[2000005]; int head[1000005], tot = 1, S, T; inline void add_e(int u, int v, int w, int cost) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot; e[tot].fl = 0; e[tot].len = w; e[tot].cost = cost;} inline void add(int u, int v, int w, int cost) {add_e(u, v, w, cost), add_e(v, u, 0, -cost);} int dis[1000005], pre[1000005]; bool vis[1000005]; bool spfa() { queue <int> Q; memset(vis, 0, sizeof vis), memset(dis, -0x3f, sizeof dis); memset(pre, 0, sizeof pre); Q.push(S), dis[S] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (e[i].len > e[i].fl && dis[v] < dis[u] + e[i].cost) { dis[v] = dis[u] + e[i].cost; pre[v] = i; if (!vis[v]) Q.push(v), vis[v] = 1; } } } return pre[T]; } int mxfl() { int cost = 0, fl = 0; while (spfa()) { int minfl = 0x3f3f3f3f; for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) minfl = min(minfl, e[i].len - e[i].fl); for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].fl += minfl, e[i ^ 1].fl -= minfl, cost += e[i].cost * minfl; fl += minfl; } return cost; } int dx[2] = {1, 0}; int dy[2] = {0, 1}; int pos[105][105], a[105][105]; int main() { int m, n, ct = 0; scanf("%d%d", &m, &n); S = 2 * m * n + 1, T = 2 * m * n + 2; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) pos[i][j] = ++ct, scanf("%d", &a[i][j]), add(pos[i][j], pos[i][j] + n * m, 1, a[i][j]), add(pos[i][j], pos[i][j] + m * n, 0x3f3f3f3f, 0); for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) { for (int t = 0; t < 2; t++) { int x = i + dx[t], y = j + dy[t]; if (x && y && x <= m && y <= n) add(pos[i][j] + n * m, pos[x][y], 0x3f3f3f3f, 0); } } add(S, 1, 2, 0), add(pos[m][n] + m * n, T, 0x3f3f3f3f, 0); printf("%d", mxfl()); }
5.[ZJOI2010 Day1]网络扩容
问题描述
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求：
1.在不扩容的情况下，1到N的最大流；
2.将1到N的最大流增加K所需的最小扩容费用。
输入格式
第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。
接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。
输出格式
包含两个整数，分别表示问题1和问题2的答案。
提示
30%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
思路：第一问求最大流，显然是模板。第二问怎么解决呢？其实发现，这个扩容费用，本质上不就是费用流吗？我们在解决问题一的时候建的是流量为C,费用为0的边。在解决问题二的时候，我们只需要重新建一次这样的边，同时，我们再加一条边，流量为inf，费用为w，利用网络流的自适应性，我们跑最小费用最大流就可以直接得出答案。
#include <bits/stdc++.h> using namespace std; //struct node { // int to, nxt, len, fl, cost; //}e[2000005]; int maxx, S, T, head[1000005], tot = 1; //inline void add_e(int u, int v, int w, int cost) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot; e[tot].len = w; e[tot].fl = 0; e[tot].cost = cost;} //inline void add(int u, int v, int w, int cost) {add_e(u, v, w, cost), add_e(v, u, 0, -cost);} struct node { int to, nxt, len, cost, fl; }e[2000005]; int head[1000005], tot = 1, S, T; inline void add_e(int u, int v, int w, int cost) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot; e[tot].len = w; e[tot].cost = cost; e[tot].fl = 0;} inline void add(int u, int v, int w, int cost) {add_e(u, v, w, cost), add_e(v, u, 0, -cost);} int dis[1000005], pre[1000005]; bool vis[1000005]; bool spfa() { queue <int> Q; memset(vis, 0, sizeof vis), memset(dis, 0x3f, sizeof dis); memset(pre, 0, sizeof pre); Q.push(S), dis[S] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (e[i].len > e[i].fl && dis[v] > dis[u] + e[i].cost) { dis[v] = dis[u] + e[i].cost; pre[v] = i; if (!vis[v]) vis[v] = 1, Q.push(v); } } } return pre[T]; } int FL, COST; void mxfl() { FL = 0, COST = 0; while (spfa()) { int minfl = 0x3f3f3f3f; for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) minfl = min(minfl, e[i].len - e[i].fl); for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].fl += minfl, e[i ^ 1].fl -= minfl, COST += e[i].cost * minfl; FL += minfl; } } int x[10005], y[10005], c[10005], w[10005], cnt[1000005]; int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= m; i++) { scanf("%d%d%d%d", &x[i], &y[i], &c[i], &w[i]); add(x[i], y[i], c[i], 0); } S = 1, T = n; mxfl(); printf("%d\n", FL); memset(head, 0, sizeof head), tot = 1; for (int i = 1; i <= m; i++) add(x[i], y[i], 0x3f3f3f3f, w[i]), add(x[i], y[i], c[i], 0); add(T, T + 1, FL + k, 0); ++T; mxfl(); printf("%d", COST); }
6.[线性规划与网络流24题 10]餐巾计划
问题描述
一个餐厅在相继的N 天里，每天需用的餐巾数不尽相同。假设第i天需要ri块餐巾(i=1，2，…，N)。餐厅可以购买新的餐巾，每块餐巾的费用为p分；或者把旧餐巾送到快洗部，洗一块需m天，其费用为f 分；或者送到慢洗部，洗一块需n 天(n>m)，其费用为s<f 分。
每天结束时，餐厅必须决定将多少块脏的餐巾送到快洗部，多少块餐巾送到慢洗部，以及多少块保存起来延期送洗。但是每天洗好的餐巾和购买的新餐巾数之和，要满足当天的需求量。
试设计一个算法为餐厅合理地安排好N 天中餐巾使用计划，使总的花费最小。
编程任务：编程找出一个最佳餐巾使用计划.
输入格式
第1 行有6 个正整数N,p,m,f,n,s。N 是要安排餐巾使用计划的天数；p 是每块新餐巾的费用；m 是快洗部洗一块餐巾需用天数；f 是快洗部洗一块餐巾需要的费用；n是慢洗部洗一块餐巾需用天数；s是慢洗部洗一块餐巾需要的费用。
接下来的N 行是餐厅在相继的N 天里，每天需用的餐巾数。
输出格式
程序运行结束时，将餐厅在相继的N 天里使用餐巾的最小总花费输出
提示
题目中所有数字都不超过1000
思路：这个题是一个相对比较考验建模的题。如果没有比较深厚的建模经验，这个题一时半会是建不出来的。
那么我们来看一看这道题的建模过程：
首先建立超源S和超汇T。
第二步，拆点，将i拆成i和i'两个点。
第三步，开始建边。S向i连（inf,p），表示每天都可以买新的餐巾。i向T连（a[i],0），表示第i天需要消耗a[i]张餐巾。S向i'连（a[i],0），表示每天会产生a[i]张旧餐巾。i'向i+1'连（inf,0），表示旧餐巾可以存放至下一天。i'向i+m连（inf,f），表示在第i天送餐巾到快洗部；同理，i'向i+n连（inf,s），作用类似。
这样的话，我们就完成了建边。
#include <bits/stdc++.h> using namespace std; int a[10005]; struct node { int to, nxt, len, cost, fl; }e[100005]; int head[50005], tot = 1, S, T; inline void add_e(int u, int v, int w, int cost) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot; e[tot].len = w; e[tot].cost = cost; e[tot].fl = 0;} inline void add(int u, int v, int w, int cost) {add_e(u, v, w, cost), add_e(v, u, 0, -cost);} int dis[50005], pre[50005]; bool vis[50005]; bool spfa() { queue <int> Q; memset(vis, 0, sizeof vis), memset(dis, 0x3f, sizeof dis); memset(pre, 0, sizeof pre); Q.push(S), dis[S] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); vis[u] = 0; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (e[i].len > e[i].fl && dis[v] > dis[u] + e[i].cost) { dis[v] = dis[u] + e[i].cost; pre[v] = i; if (!vis[v]) vis[v] = 1, Q.push(v); } } } return pre[T]; } int FL, COST; void mxfl() { FL = 0, COST = 0; while (spfa()) { int minfl = 0x3f3f3f3f; for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) minfl = min(minfl, e[i].len - e[i].fl); for (int i = pre[T]; i; i = pre[e[i ^ 1].to]) e[i].fl += minfl, e[i ^ 1].fl -= minfl, COST += e[i].cost * minfl; FL += minfl; } } int main() { int n, p, ft, f, st, s; scanf("%d%d%d%d%d%d", &n, &p, &ft, &f, &st, &s); S = 2 * n + 1, T = 2 * n + 2; for (int i = 1; i <= n; i++) scanf("%d", &a[i]); for (int i = 1; i <= n; i++) { add(S, i, 0x3f3f3f3f, p); add(S, i + n, a[i], 0); add(i, T, a[i], 0); if (i ^ n) add(i + n, i + n + 1, 0x3f3f3f3f, 0); if (i + ft <= n) add(i + n, i + ft, 0x3f3f3f3f, f); if (i + st <= n) add(i + n, i + st, 0x3f3f3f3f, s); } mxfl(); printf("%d", COST); }
暂时就鸽到这里吧。