最大流，最小割（例题收集）

题意：问能否构造一个矩阵，使得矩阵中的每个数字范围是1-20并且满足矩阵每行之和与矩阵每列之和与所给数组相等。

思路：尽管矩阵是20*20 ，但是如果爆搜复杂度依旧爆炸，我们考虑使用网络流解决这个问题，下面重点讲解怎么构图。至于怎么写可以参考紫书，与网上的模板。

建图：先来考虑本题的限制是什么，首先i行与j列存在着一个关系即共用元素k[i][j]，如果我们把数组A[i]和B[j]分别看成节点，那么意味着A[i]可以流向B[j]大小最多为k[i][j]的流量至少为1的流量,注意到，网络流中流量最小为0，所以我们可以先给每个元素减1 同时算出减完后的A’[i]与B’[j] 求出这个问题下的k’[i][j] 之后k[i][j]=k[i][j]’+1 即可，我们现在可以给A’[i]连一条通向B’[j]的容量为19的边，同时建立一个原点s ，它与每个A’[i]节点连一条边容量为A’[i]的值，建立一个汇点t ，每个B’[j]连一条通向t的边，容量为 B’[j] 跑一遍最大流，如果汇点t的流量之和为sum（B[j]）(j from 1 to m) 那么意味可以构造出来并且k’[i][j] = A’[i]到B’[j]的流量。

  1 //主代码来自刘汝佳
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 #include<vector>
  6 #include<algorithm>
  7 using namespace std;
  8 
  9 const int maxn = 50 + 5;
 10 const int INF = 1000000000;
 11 
 12 struct Edge {
 13     int from, to, cap, flow;
 14     Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f) {}
 15 };
 16 
 17 struct EdmondsKarp {
 18     int n, m;
 19     vector<Edge> edges;    // 边数的两倍
 20     vector<int> G[maxn];   // 邻接表，G[i][j]表示结点i的第j条边在e数组中的序号
 21     int a[maxn];           // 当起点到i的可改进量
 22     int p[maxn];           // 最短路树上p的入弧编号
 23 
 24     void init(int n) {
 25         for (int i = 0; i < n; i++) G[i].clear();
 26         edges.clear();
 27     }
 28 
 29     void AddEdge(int from, int to, int cap) {
 30         edges.push_back(Edge(from, to, cap, 0));
 31         edges.push_back(Edge(to, from, 0, 0));
 32         m = edges.size();
 33         G[from].push_back(m - 2);
 34         G[to].push_back(m - 1);
 35     }
 36 
 37     int Maxflow(int s, int t) {
 38         int flow = 0;
 39         for (;;) {
 40             memset(a, 0, sizeof(a));
 41             queue<int> Q;
 42             Q.push(s);
 43             a[s] = INF;
 44             while (!Q.empty()) {
 45                 int x = Q.front(); Q.pop();
 46                 for (int i = 0; i < G[x].size(); i++) {
 47                     Edge& e = edges[G[x][i]];
 48                     if (!a[e.to] && e.cap > e.flow) {
 49                         p[e.to] = G[x][i];
 50                         a[e.to] = min(a[x], e.cap - e.flow);
 51                         Q.push(e.to);
 52                     }
 53                 }
 54                 if (a[t]) break;
 55             }
 56             if (!a[t]) break;
 57             for (int u = t; u != s; u = edges[p[u]].from) {
 58                 edges[p[u]].flow += a[t];
 59                 edges[p[u] ^ 1].flow -= a[t];
 60             }
 61             flow += a[t];
 62         }
 63         return flow;
 64     }
 65 };
 66 
 67 EdmondsKarp g;
 68 int no[maxn][maxn];
 69 int a[maxn], b[maxn], str[maxn][maxn];
 70 
 71 int main() {
 72     int R, C, v, kase = 0;
 73     scanf("%d%d", &R, &C);
 74     g.init(R + C + 2);
 75     for (int i = 1; i <= R; i++) {
 76         scanf("%d", &v);
 77         g.AddEdge(0, i, v - C); // row sum is v - last
 78         a[i] = v;
 79     }
 80     int sum_b = 0;
 81     for (int i = 1; i <= C; i++) {
 82         scanf("%d", &v);
 83         g.AddEdge(R + i, R + C + 1, v - R); // col sum is v - last
 84         b[i] = v;
 85         sum_b += v;
 86     }
 87     for (int i = 1; i <= R; i++)
 88         for (int j = 1; j <= C; j++) {
 89             g.AddEdge(i, R + j, 19);
 90             no[i][j] = g.edges.size() - 2; // no[i][j] is the index of arc for cell(i,j)
 91         }
 92     g.Maxflow(0, R + C + 1);
 93 
 94 
 95     for (int i = 1; i <= R; i++)
 96         for (int j = 1; j <= C; j++)
 97             str[i][j] = g.edges[no[i][j]].flow + 1;
 98     for (int i = 1; i <= R; i++) {
 99         int sum = 0;
100         for (int j = 1; j <= C; j++) {
101             sum += str[i][j];
102             if (str[i][j] < 1 || str[i][j]>20) { printf("No
"); return 0; }
103         }
104         if (sum != a[i]) { printf("No
"); return 0; }
105     }
106     for (int j = 1; j <= C; j++) {
107         int sum = 0;
108         for (int i = 1; i <= R; i++)
109             sum += str[i][j];
110         if (sum != b[j]) { printf("No
"); return 0; }
111     }
112 
113 
114     printf("Yes
");
115     for (int i = 1; i <= R; i++) {
116         for (int j = 1; j <= C; j++)
117             printf("%d ", g.edges[no[i][j]].flow + 1); // we subtracted 1 from every cell
118         printf("
");
119     }
120     return 0;
121 }

POJ3281

题意：

N头牛，F种食物和D种饮料，每头牛都有各自喜欢的食物和饮料，而每种食物或饮料都只能分配给一头牛，最多有几头牛能同时得到喜欢的食物和饮料。

解法：

加入只求食物或饮料，那么二分图最大匹配即可，但现在情况不一样，所以我们就最大流跑一次即可，每条边上的容量为1

代码如下：

  1 struct Edge {
  2     int from, to, cap, flow;
  3 };
  4 struct Dinic {
  5     int n, m, s, t;
  6     vector<Edge> edges;
  7     vector<int> G[MAXN];
  8     bool vis[MAXN];
  9     int d[MAXN];
 10     int cur[MAXN];
 11     void init() {
 12         for (int i = 0; i < MAXN; i++) G[i].clear();
 13         edges.clear();
 14         memset(d, 0, sizeof(d));
 15     }
 16     void AddEdge(int from, int to, int cap) {
 17         edges.push_back({from, to, cap, 0});
 18         edges.push_back({to, from, 0, 0});
 19         m = edges.size();
 20         G[from].push_back(m - 2);
 21         G[to].push_back(m - 1);
 22     }
 23     bool BFS() {
 24         int x, i;
 25         memset(vis, 0, sizeof(vis));
 26         queue<int> Q;
 27         Q.push(s);
 28         d[s] = 0;
 29         vis[s] = 1;
 30         while (!Q.empty()) {
 31             x = Q.front(), Q.pop();
 32             for (i = 0; i < G[x].size(); i++) {
 33                 Edge &e = edges[G[x][i]];
 34                 if (!vis[e.to] && e.cap > e.flow) {
 35                     vis[e.to] = 1;
 36                     d[e.to] = d[x] + 1;
 37                     Q.push(e.to);
 38                 }
 39             }
 40         }
 41         return vis[t];
 42     }
 43     int DFS(int x, int a) {
 44         if (x == t || a == 0) return a;
 45         int flow = 0, f;
 46         for (int &i = cur[x]; i < G[x].size(); i++) {
 47             Edge &e = edges[G[x][i]];
 48             if (d[x] + 1 == d[e.to] &&
 49                 (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
 50                 e.flow += f;
 51                 edges[G[x][i] ^ 1].flow -= f;
 52                 flow += f;
 53                 a -= f;
 54                 if (a == 0) break;
 55             }
 56         }
 57         return flow;
 58     }
 59     int Maxflow(int s, int t) {
 60         this->s = s, this->t = t;
 61         int flow = 0;
 62         while (BFS()) {
 63             memset(cur, 0, sizeof(cur));
 64             flow += DFS(s, INF);
 65         }
 66         return flow;
 67     }
 68 } Men;
 69 
 70 int N, F, D;
 71 int cnt;
 72 vector<int> food[102];
 73 vector<int> drink[102];
 74 map<int, int> fd, cow1, cow2, dk;
 75 
 76 void encode() {
 77     cnt = 0;
 78     REP(i, 1, F) fd[i] = ++cnt;
 79     REP(i, 1, N) cow1[i] = ++cnt;
 80     REP(i, 1, N) cow2[i] = ++cnt;
 81     REP(i, 1, D) dk[i] = ++cnt;
 82     ++cnt;
 83 }
 84 
 85 void solve() {
 86     encode();
 87 
 88     Men.init();
 89     int s = 0, t = cnt;
 90 
 91     // source to food
 92     for (int i = 1; i <= F; i++) {
 93         Men.AddEdge(s, fd[i], 1);
 94     }
 95 
 96     // food to cow1
 97     for (int i = 1; i <= F; i++) {
 98         for (int j = 0; j < food[i].size(); j++) {
 99             Men.AddEdge(fd[i], cow1[food[i][j]], 1);
100         }
101     }
102 
103     // cow1 to cow2
104     for (int i = 1; i <= N; i++) {
105         Men.AddEdge(cow1[i], cow2[i], 1);
106         // cow2 to drink
107         for (int j = 0; j < drink[i].size(); j++) {
108             Men.AddEdge(cow2[i], dk[drink[i][j]], 1);
109         }
110     }
111 
112     // cow2 to target
113     for (int i = 1; i <= D; i++) {
114         Men.AddEdge(dk[i], t, 1);
115     }
116 
117     cout << Men.Maxflow(s, t) << endl;
118 
119     return;
120 }
121 
122 int main() {
123 #ifndef ONLINE_JUDGE
124     freopen("input.txt", "r", stdin);
125 #endif  // !ONLINE_JUDGE
126     N = READ(), F = READ(), D = READ();
127     REP(i, 1, N) {
128         int f = READ(), d = READ();
129         REP(j, 1, f) {
130             int o = READ();
131             food[o].push_back(i);
132         }
133         REP(j, 1, d) {
134             int o = READ();
135             drink[i].push_back(o);
136         }
137     }
138     solve();
139     return 0;
140 }