题目大意
「WF 2012」Chips Challenge（UVA 1104）
给定一个 $n \times n$ 的棋盘，有些格子已经放上了黑色或白色的棋子。要求你在剩下的格子中摆放棋子，满足条件：
- 第 $i$ 行的黑子个数等于第 $i$ 列的黑子个数。
- 每行的黑子个数不大于总黑子个数的 $\frac{A}{B}$。
求最多再放多少黑子。
数据范围：$n \le 50$。
思路分析
枚举每行每列最多放 $k$ 枚黑子，这样第二个限制就变成了总黑子数量不能超过 $\frac{B \cdot k}{A}$。
考虑建图：
- $S$ 向 $R_i$ 连边，代价为 $0$，流量为这一行最多可能摆放的黑子数量。
- $C_i$ 向 $T$ 连边，代价为 $0$，流量为这一列最多可能摆放的黑子数量。
- $R_i$ 向 $C_i$ 连边，代价为 $0$，流量为 $k$。
- 如果 $(i, j)$ 可以不放零件，那么 $R_i$ 向 $C_j$ 连边，代价为 $1$，流量为 $1$。
图中流量的含义：先走第 $4$ 类边表示放置白子，之后如果有可行解，那么残量网络必定左右对称并且和 $S, T$ 相邻的边的的容量都不大于 $k$，这样就可以给剩下的格子全部放上黑子。
于是我们可以发现，如果网络满流，就形成了一个可行方案。而满流情况下最小的费用就是最少放置白子的数量。
时间复杂度 $O(n \times \text{MCMF}(n, n^2))$。
代码实现
1 | |
2 | |
3 | |
4 | using namespace std; |
5 | |
6 | const int maxn = 50, maxv = 102, maxe = 2 * maxn * (maxn + 3); |
7 | char s[maxn + 3]; |
8 | int T, n, A, B, a[maxn + 3][maxn + 3], Rc[maxn + 3], Cc[maxn + 3]; |
9 | int tot, ter[maxe + 3], nxt[maxe + 3], len[maxe + 3], wei[maxe + 3], lnk[maxv + 3]; |
10 | |
11 | void add_edge(int u, int v, int w, int l) { |
12 | ter[++tot] = v, wei[tot] = w, len[tot] = l; |
13 | nxt[tot] = lnk[u], lnk[u] = tot; |
14 | } |
15 | |
16 | void add_fedge(int u, int v, int w, int l) { |
17 | add_edge(u, v, w, l), add_edge(v, u, 0, -l); |
18 | } |
19 | |
20 | inline int adj(int x) { |
21 | return x & 1 ? x + 1 : x - 1; |
22 | } |
23 | |
24 | namespace mcmf { |
25 | int sz, src, snk; |
26 | queue<int> Q; |
27 | bool in[maxv + 3]; |
28 | int dist[maxv + 3], lst[maxv + 3], mn[maxv + 3]; |
29 | void init(int n, int s, int t) { |
30 | sz = n, src = s, snk = t; |
31 | } |
32 | bool solve(int &mc, int &mf) { |
33 | memset(dist, 0x3f, sizeof(dist)); |
34 | memset(lst, 0, sizeof(lst)); |
35 | memset(mn, 0x3f, sizeof(mn)); |
36 | dist[src] = 0, in[src] = true, Q.push(src); |
37 | while (!Q.empty()) { |
38 | int u = Q.front(); |
39 | in[u] = false, Q.pop(); |
40 | for (int i = lnk[u], v, w, l; i; i = nxt[i]) { |
41 | v = ter[i], w = wei[i], l = len[i]; |
42 | if (w && dist[u] + l < dist[v]) { |
43 | dist[v] = dist[u] + l, lst[v] = i, mn[v] = min(mn[u], w); |
44 | if (!in[v]) in[v] = true, Q.push(v); |
45 | } |
46 | } |
47 | } |
48 | if (!lst[snk]) return false; |
49 | mf = mn[snk], mc = mf * dist[snk]; |
50 | int x = snk; |
51 | while (x != src) { |
52 | wei[lst[x]] -= mf; |
53 | wei[adj(lst[x])] += mf; |
54 | x = ter[adj(lst[x])]; |
55 | } |
56 | return true; |
57 | } |
58 | void main(int &mc, int &mf) { |
59 | mc = mf = 0; |
60 | int cc = 0, cf = 0; |
61 | while (solve(cc, cf)) { |
62 | mc += cc, mf += cf; |
63 | } |
64 | } |
65 | } |
66 | |
67 | int main() { |
68 | while (scanf("%d %d %d", &n, &A, &B), n) { |
69 | for (int i = 1; i <= n; i++) { |
70 | scanf("%s", s + 1); |
71 | for (int j = 1; j <= n; j++) { |
72 | a[i][j] = s[j] == '.' ? -1 : s[j] == '/' ? 0 : 1; |
73 | } |
74 | } |
75 | for (int i = 1; i <= n; i++) { |
76 | Rc[i] = Cc[i] = 0; |
77 | } |
78 | int cnt = 0, sum = 0; |
79 | for (int i = 1; i <= n; i++) { |
80 | for (int j = 1; j <= n; j++) { |
81 | if (a[i][j]) { |
82 | Rc[i]++, Cc[j]++, sum++; |
83 | if (a[i][j] == 1) cnt++; |
84 | } |
85 | } |
86 | } |
87 | int s = 2 * n + 1, t = s + 1, ans = -1; |
88 | for (int k = 0; k <= n; k++) { |
89 | tot = 0; |
90 | memset(lnk, 0, sizeof(lnk)); |
91 | mcmf::init(t, s, t); |
92 | for (int i = 1; i <= n; i++) { |
93 | add_fedge(s, i, Rc[i], 0); |
94 | add_fedge(i, i + n, k, 0); |
95 | add_fedge(i + n, t, Cc[i], 0); |
96 | } |
97 | for (int i = 1; i <= n; i++) { |
98 | for (int j = 1; j <= n; j++) { |
99 | if (a[i][j] == -1) { |
100 | add_fedge(i, j + n, 1, 1); |
101 | } |
102 | } |
103 | } |
104 | int mc = 0, mf = 0; |
105 | mcmf::main(mc, mf); |
106 | if (mf == sum && B * k <= A * (sum - mc)) { |
107 | ans = max(ans, sum - cnt - mc); |
108 | } |
109 | } |
110 | printf("Case %d: ", ++T); |
111 | if (~ans) printf("%d\n", ans); |
112 | else puts("impossible"); |
113 | } |
114 | return 0; |
115 | } |