BZOJ2673: [Wf2011]Chips Challenge 网络流+费用流

题目大意：

反正已经有翻译了，就自己去看咯。

算法讨论：

首先是每行每列都有一个跟答案相关的限制，但是我们并不知道答案，所以我们可以枚举这个限制，算出在这个限制下的答案，然后比较在这个答案下的限制和枚举的限制，若前者不小于后者则可以认为这个答案是合法的。最终的答案一定会出现在这些合法的答案中。

不难想到把$n$行$n$列拆成$2n$个点，然后从$S$到左侧的行点，从右侧的列点到$T$各连接一条流量为枚举的限制费用为$0$的边。然后对于第$i$行第$j$列，从左侧的第$i$个行点到右侧的第$j$个列点连边，若为'.'则连接一条流量为$1$费用为$1$的边，若为'C'则连接一条流量下界为1上界为1费用为1的边，若为'/'则什么也不连。

但是还需要满足的是第$i$行和第$i$列的零件数目相等。

我们考虑一种连边：从第$i$个行点到第$i$个列点连一条流量为$\infty$费用为$0$的边，然后求这个网络的最大费用最大流就是答案。

这样是怎样保证数目相等这个限制的呢？

可以发现现在流网络的最大流必为$n\times{枚举的限制}$。这是在不考虑任何零件的边之后得到的。那么对于第$i$个行点，设当前枚举限制为$c$，他本应该把从$S$流来的$c$流量，通过那条$\infty$边全部流到第$i$个列点，随后全部流到$T$。但是第$i$个行点可能向一些列节点流了一些流量（放置零件），假设为$x$（那么此时第$i$行就放了$x$个零件），那么他就只能有$c-x$的流量通过上述途径流到$T$，于是此时第$i$个列点与$T$之间的边就只流了$c-x$的流量，但是最大流时这条边必须满流，那么剩下的$x$流量从哪里来呢？必定是有$x$个行点流向了这个列点将这$x$流量流向了$T$，因此第$i$列也放了$x$个零件。这就证明了这样建模的正确性。

到此时已经可以使用上下界网络流来解决问题。但在这道问题中，我们也可以使用一些技巧，我们将必须放的零件的费用设为$1+10000$（由于$10000>40\times{40}$所以不会产生什么影响），然后求最大费用最大流，如果所有的$10000$都在费用中了，证明存在合法解，费用对$10000$取模的余数就是答案；否则在最大流意义下有些必须放的零件没有放，证明无解。

这样已经可以通过这道题目。

对于存在负权环的流网络，我们可以用类似的方式预先建模将所有的负权环流满并删去，然后做正常的最小费用流即可。

将每个点拆为入点和出点，我们只需要流一些流，使得每个点入点流入的恰等于出点流出的，这样就一定能拆成若干个环。这种相等的限制用刚才的方法建模求最小费用最大流即可。

另：感觉裸上单纯形就可以，但是不知道能不能过，应该可以吧。

代码：

#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long ll;
static const int inf = 0x3f3f3f3f;
struct Solver {
	static const int V = 110;
	static const int E = 10010;
	int head[V], nxt[E], to[E], flow[E], cost[E], lv[V], le[V], dis[V], ind;
	queue<int> q;
	bool inq[V];
	void reset() {
		memset(head, -1, sizeof head);
		ind = 0;
	}
	void addedge(int u, int v, int f, int c) {
		int q = ind++;
		to[q] = v;
		nxt[q] = head[u];
		head[u] = q;
		flow[q] = f;
		cost[q] = c;
	}
	void make(int u, int v, int f, int c) {
		addedge(u, v, f, c);
		addedge(v, u, 0, -c);
	}
	bool spfa(int s, int t) {
		memset(dis, 0xc0, sizeof dis);
		dis[s] = 0;
		q.push(s);
		inq[s] = 1;
		int i, j;
		while (!q.empty()) {
			i = q.front();
			q.pop();
			inq[i] = 0;
			for (j = head[i]; j != -1; j = nxt[j]) {
				if (flow[j] && dis[to[j]] < dis[i] + cost[j]) {
					lv[to[j]] = i;
					le[to[j]] = j;
					dis[to[j]] = dis[i] + cost[j];
					if (!inq[to[j]]) {
						q.push(to[j]);
						inq[to[j]] = 1;
					}
				}
			}
		}
		return dis[t] != 0xc0c0c0c0;
	}
	int MCMF(int s, int t) {
		int i, j, mn, tc = 0;
		while (spfa(s, t)) {
			for (mn = inf, i = t; i != s; i = lv[i])
				mn = min(mn, flow[le[i]]);
			for (tc += (ll)mn * dis[t], i = t; i != s; i = lv[i]) {
				flow[le[i]] -= mn;
				flow[le[i] ^ 1] += mn;
			}
		}
		return tc;
	}
}g;

#define N 41
char S[N][N];

int main() {
	//freopen("chips1.in", "r", stdin);
	//freopen("chips.in", "r", stdin);
	//freopen("chips.out", "w", stdout);
	int Case = 0, n, A, B, i, j;
	while (scanf("%d%d%d", &n, &A, &B) && (n + A + B)) {
		int numberC = 0;
		for (i = 1; i <= n; ++i) {
			scanf("%s", S[i] + 1);
			for (j = 1; j <= n; ++j) {
				if (S[i][j] == 'C')
					++numberC;
			}
		}
		int temp, mx = 0;
		for (i = 1; i <= n; ++i) {
			for (temp = 0, j = 1; j <= n; ++j)
				temp += S[i][j] == 'C';
			mx = max(mx, temp);
		}
		for (j = 1; j <= n; ++j) {
			for (temp = 0, i = 1; i <= n; ++i)
				temp += S[i][j] == 'C';
			mx = max(mx, temp);
		}
		int ans = -1, s = 0, t = 2 * n + 1;
		for (int lim = mx; lim <= n; ++lim) {
			g.reset();
			for (i = 1; i <= n; ++i) {
				g.make(s, i, lim, 0);
				g.make(i + n, t, lim, 0);
				g.make(i, i + n, inf, 0);
			}
			for (i = 1; i <= n; ++i) {
				for (j = 1; j <= n; ++j) {
					if (S[i][j] == '/')
						continue;
					g.make(i, j + n, 1, 1 + (S[i][j] == 'C' ? 10000 : 0));
				}
			}
			int cost = g.MCMF(s, t);
			if (cost / 10000 != numberC)
				continue;
			if (A * (cost %= 10000) / B >= lim)
				ans = max(ans, cost - numberC);
		}
		printf("Case %d: ", ++Case);
		if (ans == -1)
			puts("impossible");
		else
			printf("%d\n", ans);
		//break;
	}
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

---滑稽摇摆---