「WF 2012」Chips Challenge（费用流）

发表于 |

题目大意

「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
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

const int maxn = 50, maxv = 102, maxe = 2 * maxn * (maxn + 3);
char s[maxn + 3];
int T, n, A, B, a[maxn + 3][maxn + 3], Rc[maxn + 3], Cc[maxn + 3];
int tot, ter[maxe + 3], nxt[maxe + 3], len[maxe + 3], wei[maxe + 3], lnk[maxv + 3];

void add_edge(int u, int v, int w, int l) {
	ter[++tot] = v, wei[tot] = w, len[tot] = l;
	nxt[tot] = lnk[u], lnk[u] = tot;
}

void add_fedge(int u, int v, int w, int l) {
	add_edge(u, v, w, l), add_edge(v, u, 0, -l);
}

inline int adj(int x) {
	return x & 1 ? x + 1 : x - 1;
}

namespace mcmf {
	int sz, src, snk;
	queue<int> Q;
	bool in[maxv + 3];
	int dist[maxv + 3], lst[maxv + 3], mn[maxv + 3];
	void init(int n, int s, int t) {
		sz = n, src = s, snk = t;
	}
	bool solve(int &mc, int &mf) {
		memset(dist, 0x3f, sizeof(dist));
		memset(lst, 0, sizeof(lst));
		memset(mn, 0x3f, sizeof(mn));
		dist[src] = 0, in[src] = true, Q.push(src);
		while (!Q.empty()) {
			int u = Q.front();
			in[u] = false, Q.pop();
			for (int i = lnk[u], v, w, l; i; i = nxt[i]) {
				v = ter[i], w = wei[i], l = len[i];
				if (w && dist[u] + l < dist[v]) {
					dist[v] = dist[u] + l, lst[v] = i, mn[v] = min(mn[u], w);
					if (!in[v]) in[v] = true, Q.push(v);
				}
			}
		}
		if (!lst[snk]) return false;
		mf = mn[snk], mc = mf * dist[snk];
		int x = snk;
		while (x != src) {
			wei[lst[x]] -= mf;
			wei[adj(lst[x])] += mf;
			x = ter[adj(lst[x])];
		}
		return true;
	}
	void main(int &mc, int &mf) {
		mc = mf = 0;
		int cc = 0, cf = 0;
		while (solve(cc, cf)) {
			mc += cc, mf += cf;
		}
	}
}

int main() {
	while (scanf("%d %d %d", &n, &A, &B), n) {
		for (int i = 1; i <= n; i++) {
			scanf("%s", s + 1);
			for (int j = 1; j <= n; j++) {
				a[i][j] = s[j] == '.' ? -1 : s[j] == '/' ? 0 : 1; 
			}
		}
		for (int i = 1; i <= n; i++) {
			Rc[i] = Cc[i] = 0;
		}
		int cnt = 0, sum = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (a[i][j]) {
					Rc[i]++, Cc[j]++, sum++;
					if (a[i][j] == 1) cnt++;
				}
			}
		}
		int s = 2 * n + 1, t = s + 1, ans = -1;
		for (int k = 0; k <= n; k++) {
			tot = 0;
			memset(lnk, 0, sizeof(lnk));
			mcmf::init(t, s, t);
			for (int i = 1; i <= n; i++) {
				add_fedge(s, i, Rc[i], 0);
				add_fedge(i, i + n, k, 0);
				add_fedge(i + n, t, Cc[i], 0);
			}
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					if (a[i][j] == -1) {
						add_fedge(i, j + n, 1, 1);
					}
				}
			}
			int mc = 0, mf = 0;
			mcmf::main(mc, mf);
			if (mf == sum && B * k <= A * (sum - mc)) {
				ans = max(ans, sum - cnt - mc);
			}
		}
		printf("Case %d: ", ++T);
		if (~ans) printf("%d\n", ans);
		else puts("impossible");
	}
	return 0;
}