最小割

佚名 6年前 (2019-04-18) 随笔 1117人围观抢沙发百度已收录

复习一波最小割...

BZOJ1934 善意的投票

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题意：n个人分别喜欢睡/不睡午觉。改变一个人的喜好要花费1代价。有m对朋友，每对朋友的喜好不同会产生1代价。求最小代价。

解：经典题了.....

每个人向s，t连边，求最小割。如果割掉某个边就代表选哪边。朋友之间连双向边，代表如果选的不同的话还要割一刀。

考虑为什么不会有点两条边都被割。因为两条边都被割表明有个跟它相连的没割上面，又有个跟它相连的没割下面，而这显然是不可能的，因为它们会通过这个点间接的出现一条流。

 1 #include <bits/stdc++.h>
 2 
 3 const int N = 3010, INF = 0x3f3f3f3f;
 4 
 5 struct Edge {
 6     int nex, v, c;
 7     Edge(int NEX = 0, int V = 0, int C = 0) {
 8         nex = NEX;
 9         v = V;
10         c = C;
11     }
12 }edge[2000010]; int tp = 1;
13 
14 int e[N], d[N], vis[N], Time, cur[N], cnt;
15 std::queue<int> Q;
16 int n, a[N];
17 
18 inline void add(int x, int y, int z) {
19     edge[++tp] = Edge(e[x], y, z);
20     e[x] = tp;
21     edge[++tp] = Edge(e[y], x, 0);
22     e[y] = tp;
23     return;
24 }
25 
26 inline bool BFS(int s, int t) {
27     Time++;
28     vis[s] = Time;
29     d[s] = 0;
30     Q.push(s);
31     while(Q.size()) {
32         int x = Q.front();
33         Q.pop();
34         for(int i = e[x]; i; i = edge[i].nex) {
35             int y = edge[i].v;
36             if(vis[y] == Time || !edge[i].c) continue;
37             vis[y] = Time;
38             d[y] = d[x] + 1;
39             Q.push(y);
40         }
41     }
42     return vis[t] == Time;
43 }
44 
45 int DFS(int x, int t, int maxF) {
46     if(x == t) return maxF;
47     int ans = 0;
48     for(int i = cur[x]; i; i = edge[i].nex) {
49         int y = edge[i].v;
50         if(d[y] != d[x] + 1 || !edge[i].c) continue;
51         int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
52         if(!temp) d[y] = INF;
53         ans += temp;
54         edge[i].c -= temp;
55         edge[i ^ 1].c += temp;
56         if(ans == maxF) break;
57         cur[x] = i;
58     }
59     return ans;
60 }
61 
62 inline int solve(int s, int t) {
63     int ans = 0;
64     while(BFS(s, t)) {
65         memcpy(cur + 1, e + 1, cnt * sizeof(int));
66         ans += DFS(s, t, INF);
67     }
68     return ans;
69 }
70 
71 int main() {
72     int m;
73     scanf("%d%d", &n, &m);
74     int s = n + 1, t = n + 2;
75     cnt = t;
76     for(int i = 1; i <= n; i++) {
77         scanf("%d", &a[i]);
78         if(a[i]) {
79             add(s, i, 1);
80         }
81         else {
82             add(i, t, 1);
83         }
84     }
85     for(int i = 1, x, y; i <= m; i++) {
86         scanf("%d%d", &x, &y);
87         add(x, y, 1);
88         add(y, x, 1);
89     }
90     int ans = solve(s, t);
91     printf("%d\n", ans);
92     return 0;
93 }

AC代码

BZOJ2127 happiness

题意：n个人，m对朋友。每个人选文科，理科都分别有贡献，每对朋友同时选文/选理也有贡献。求最大贡献。

解：先设每个人同时选了文理。考虑割掉。

s向人连选文的贡献，人向t连选理的。一对朋友之间，考虑到如果有任一个选了文，就拿不到全选理的贡献，所以建图大概长这样...

然后求最小割，拿总贡献减去，就是最大贡献了。

  1 #include <bits/stdc++.h>
  2 
  3 const int N = 100010, INF = 0x3f3f3f3f;
  4 
  5 struct Edge {
  6     int nex, v, c;
  7     Edge(int NEX = 0, int V = 0, int C = 0) {
  8         nex = NEX;
  9         v = V;
 10         c = C;
 11     }
 12 }edge[2000010]; int tp = 1;
 13 
 14 int e[N], d[N], vis[N], Time, cur[N], cnt;
 15 std::queue<int> Q;
 16 int n, m, s, t;
 17 
 18 inline void add(int x, int y, int z) {
 19     edge[++tp] = Edge(e[x], y, z);
 20     e[x] = tp;
 21     edge[++tp] = Edge(e[y], x, 0);
 22     e[y] = tp;
 23     return;
 24 }
 25 
 26 inline bool BFS(int s, int t) {
 27     Time++;
 28     vis[s] = Time;
 29     d[s] = 0;
 30     Q.push(s);
 31     while(Q.size()) {
 32         int x = Q.front();
 33         Q.pop();
 34         for(int i = e[x]; i; i = edge[i].nex) {
 35             int y = edge[i].v;
 36             if(vis[y] == Time || !edge[i].c) continue;
 37             vis[y] = Time;
 38             d[y] = d[x] + 1;
 39             Q.push(y);
 40         }
 41     }
 42     return vis[t] == Time;
 43 }
 44 
 45 int DFS(int x, int t, int maxF) {
 46     if(x == t) return maxF;
 47     int ans = 0;
 48     for(int i = cur[x]; i; i = edge[i].nex) {
 49         int y = edge[i].v;
 50         if(d[y] != d[x] + 1 || !edge[i].c) continue;
 51         int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
 52         if(!temp) d[y] = INF;
 53         ans += temp;
 54         edge[i].c -= temp;
 55         edge[i ^ 1].c += temp;
 56         if(ans == maxF) break;
 57         cur[x] = i;
 58     }
 59     return ans;
 60 }
 61 
 62 inline int solve(int s, int t) {
 63     int ans = 0;
 64     while(BFS(s, t)) {
 65         memcpy(cur + 1, e + 1, cnt * sizeof(int));
 66         ans += DFS(s, t, INF);
 67     }
 68     return ans;
 69 }
 70 
 71 inline int id(int i, int j) {
 72     return (i - 1) * m + j;
 73 }
 74 
 75 int main() {
 76     scanf("%d%d", &n, &m);
 77     s = n * m + 1, t = s + 1;
 78     int ans = 0, x;
 79     cnt = t;
 80     for(int i = 1; i <= n; i++) {
 81         for(int j = 1; j <= m; j++) {
 82             scanf("%d", &x);
 83             ans += x;
 84             add(s, id(i, j), x);
 85         }
 86     }
 87     for(int i = 1; i <= n; i++) {
 88         for(int j = 1; j <= m; j++) {
 89             scanf("%d", &x);
 90             ans += x;
 91             add(id(i, j), t, x);
 92         }
 93     }
 94     for(int i = 1; i < n; i++) {
 95         for(int j = 1; j <= m; j++) {
 96             scanf("%d", &x);
 97             ans += x;
 98             add(s, ++cnt, x);
 99             add(cnt, id(i, j), INF);
100             add(cnt, id(i + 1, j), INF);
101         }
102     }
103     for(int i = 1; i < n; i++) {
104         for(int j = 1; j <= m; j++) {
105             scanf("%d", &x);
106             ans += x;
107             add(++cnt, t, x);
108             add(id(i, j), cnt, INF);
109             add(id(i + 1, j), cnt, INF);
110         }
111     }
112     for(int i = 1; i <= n; i++) {
113         for(int j = 1; j < m; j++) {
114             scanf("%d", &x);
115             ans += x;
116             add(s, ++cnt, x);
117             add(cnt, id(i, j), INF);
118             add(cnt, id(i, j + 1), INF);
119         }
120     }
121     for(int i = 1; i <= n; i++) {
122         for(int j = 1; j < m; j++) {
123             scanf("%d", &x);
124             ans += x;
125             add(++cnt, t, x);
126             add(id(i, j), cnt, INF);
127             add(id(i, j + 1), cnt, INF);
128         }
129     }
130     ans -= solve(s, t);
131     printf("%d\n", ans);
132     return 0;
133 }

AC代码

注意这题建图画风跟别的题不一样，是因为按照之前的建图，当一对朋友同时选0的时候，仍要损失同时选1的代价，而这部分是我们难以计算的。

BZOJ1976 能量魔方

题意：有n³个块构成了立方体，有些位置填了0/1，别的地方自己填。6连通的块之间如果颜色不同就会有1贡献，求最大贡献。

解：前两题都是最大化相同，最小化不同，这题反其道而行之，何如？

考虑到这些格子和6连通关系构成了二分图。我们把其中一个部分全部反色，不就成了最大化相同吗？直接套用第一题的做法。

  1 #include <bits/stdc++.h>
  2 
  3 const int N = 100010, INF = 0x3f3f3f3f;
  4 
  5 struct Edge {
  6     int nex, v, c;
  7     Edge(int NEX = 0, int V = 0, int C = 0) {
  8         nex = NEX;
  9         v = V;
 10         c = C;
 11     }
 12 }edge[2000010]; int tp = 1;
 13 
 14 int e[N], d[N], vis[N], Time, cur[N], cnt;
 15 std::queue<int> Q;
 16 int n;
 17 
 18 inline void add(int x, int y, int z) {
 19     edge[++tp] = Edge(e[x], y, z);
 20     e[x] = tp;
 21     edge[++tp] = Edge(e[y], x, 0);
 22     e[y] = tp;
 23     return;
 24 }
 25 
 26 inline bool BFS(int s, int t) {
 27     Time++;
 28     vis[s] = Time;
 29     d[s] = 0;
 30     Q.push(s);
 31     while(Q.size()) {
 32         int x = Q.front();
 33         Q.pop();
 34         for(int i = e[x]; i; i = edge[i].nex) {
 35             int y = edge[i].v;
 36             if(vis[y] == Time || !edge[i].c) continue;
 37             vis[y] = Time;
 38             d[y] = d[x] + 1;
 39             Q.push(y);
 40         }
 41     }
 42     return vis[t] == Time;
 43 }
 44 
 45 int DFS(int x, int t, int maxF) {
 46     if(x == t) return maxF;
 47     int ans = 0;
 48     for(int i = cur[x]; i; i = edge[i].nex) {
 49         int y = edge[i].v;
 50         if(d[y] != d[x] + 1 || !edge[i].c) continue;
 51         int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
 52         if(!temp) d[y] = INF;
 53         ans += temp;
 54         edge[i].c -= temp;
 55         edge[i ^ 1].c += temp;
 56         if(ans == maxF) break;
 57         cur[x] = i;
 58     }
 59     return ans;
 60 }
 61 
 62 inline int solve(int s, int t) {
 63     int ans = 0;
 64     while(BFS(s, t)) {
 65         memcpy(cur + 1, e + 1, cnt * sizeof(int));
 66         ans += DFS(s, t, INF);
 67     }
 68     return ans;
 69 }
 70 
 71 inline int id(int x, int y, int z) {
 72     return (x - 1) * n * n + (y - 1) * n + z;
 73 }
 74 
 75 char str[N];
 76 
 77 int main() {
 78     scanf("%d", &n);
 79     int s = n * n * n + 1, t = s + 1, ans = 0;
 80     cnt = t;
 81     for(int i = 1; i <= n; i++) {
 82         for(int j = 1; j <= n; j++) {
 83             scanf("%s", str + 1);
 84             for(int k = 1; k <= n; k++) {
 85                 if(str[k] == '?');
 86                 else if((str[k] == 'P') == ((i + j + k) & 1)) {
 87                     add(s, id(i, j, k), INF);
 88                 }
 89                 else {
 90                     add(id(i, j, k), t, INF);
 91                 }
 92 
 93                 if(i > 1) {
 94                     add(id(i, j, k), id(i - 1, j, k), 1);
 95                     add(id(i - 1, j, k), id(i, j, k), 1);
 96                     ans++;
 97                 }
 98                 if(j > 1) {
 99                     add(id(i, j, k), id(i, j - 1, k), 1);
100                     add(id(i, j - 1, k), id(i, j, k), 1);
101                     ans++;
102                 }
103                 if(k > 1) {
104                     add(id(i, j, k), id(i, j, k - 1), 1);
105                     add(id(i, j, k - 1), id(i, j, k), 1);
106                     ans++;
107                 }
108             }
109         }
110     }
111     printf("%d\n", ans - solve(s, t));
112     return 0;
113 }

AC代码

BZOJ2132 圈地计划

题意：给你一个矩阵，每个位置放0有贡献，放1有贡献，4连通的格子放不同的还有贡献，求最大贡献。

解：类似上一题，黑白染色之后把黑色格子放的全部反转，就有相同相邻的格子会产生贡献。注意01分别的贡献也要相应的反转。

然后使用上一题的做法即可。

  1 #include <bits/stdc++.h>
  2 
  3 const int N = 100010, INF = 0x3f3f3f3f;
  4 
  5 struct Edge {
  6     int nex, v, c;
  7     Edge(int NEX = 0, int V = 0, int C = 0) {
  8         nex = NEX;
  9         v = V;
 10         c = C;
 11     }
 12 }edge[2000010]; int tp = 1;
 13 
 14 int e[N], d[N], vis[N], Time, cur[N], cnt;
 15 std::queue<int> Q;
 16 int n, m, a[101][101], b[101][101], c[101][101];
 17 
 18 inline void add(int x, int y, int z) {
 19     edge[++tp] = Edge(e[x], y, z);
 20     e[x] = tp;
 21     edge[++tp] = Edge(e[y], x, 0);
 22     e[y] = tp;
 23     return;
 24 }
 25 
 26 inline bool BFS(int s, int t) {
 27     Time++;
 28     vis[s] = Time;
 29     d[s] = 0;
 30     Q.push(s);
 31     while(Q.size()) {
 32         int x = Q.front();
 33         Q.pop();
 34         for(int i = e[x]; i; i = edge[i].nex) {
 35             int y = edge[i].v;
 36             if(vis[y] == Time || !edge[i].c) continue;
 37             vis[y] = Time;
 38             d[y] = d[x] + 1;
 39             Q.push(y);
 40         }
 41     }
 42     return vis[t] == Time;
 43 }
 44 
 45 int DFS(int x, int t, int maxF) {
 46     if(x == t) return maxF;
 47     int ans = 0;
 48     for(int i = cur[x]; i; i = edge[i].nex) {
 49         int y = edge[i].v;
 50         if(d[y] != d[x] + 1 || !edge[i].c) continue;
 51         int temp = DFS(y, t, std::min(edge[i].c, maxF - ans));
 52         if(!temp) d[y] = INF;
 53         ans += temp;
 54         edge[i].c -= temp;
 55         edge[i ^ 1].c += temp;
 56         if(ans == maxF) break;
 57         cur[x] = i;
 58     }
 59     return ans;
 60 }
 61 
 62 inline int solve(int s, int t) {
 63     int ans = 0;
 64     while(BFS(s, t)) {
 65         memcpy(cur + 1, e + 1, cnt * sizeof(int));
 66         ans += DFS(s, t, INF);
 67     }
 68     return ans;
 69 }
 70 
 71 inline int id(int i, int j) {
 72     return (i - 1) * m + j;
 73 }
 74 
 75 int main() {
 76     scanf("%d%d", &n, &m);
 77     int s = n * m + 1, t = s + 1, ans = 0;
 78     cnt = t;
 79     for(int i = 1; i <= n; i++) {
 80         for(int j = 1; j <= m; j++) {
 81             scanf("%d", &a[i][j]);
 82             ans += a[i][j];
 83         }
 84     }
 85     for(int i = 1; i <= n; i++) {
 86         for(int j = 1; j <= m; j++) {
 87             scanf("%d", &b[i][j]);
 88             ans += b[i][j];
 89             if((i + j) & 1) {
 90                 std::swap(a[i][j], b[i][j]);
 91             }
 92             add(s, id(i, j), a[i][j]);
 93             add(id(i, j), t, b[i][j]);
 94         }
 95     }
 96     for(int i = 1; i <= n; i++) {
 97         for(int j = 1; j <= m; j++) {
 98             scanf("%d", &c[i][j]);
 99             if(i > 1) {
100                 add(id(i, j), id(i - 1, j), c[i][j] + c[i - 1][j]);
101                 add(id(i - 1, j), id(i, j), c[i][j] + c[i - 1][j]);
102                 ans += c[i][j] + c[i - 1][j];
103             }
104             if(j > 1) {
105                 add(id(i, j), id(i, j - 1), c[i][j] + c[i][j - 1]);
106                 add(id(i, j - 1), id(i, j), c[i][j] + c[i][j - 1]);
107                 ans += c[i][j] + c[i][j - 1];
108             }
109         }
110     }
111 
112     printf("%d\n", ans - solve(s, t));
113 
114     return 0;
115 }