自动搬运

查看原文

来自洛谷，原作者为

	GGN_2015 车道山前必有路，钱到月底不够花。

搬运于2025-08-24 21:58:51，当前版本为作者最后更新于2018-04-04 11:44:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题用上下界网络流可能有点大材小用了，其实一个普通的网络流就能解决问题。首先考虑逆向思维，求最少要使用的士兵个数，转化为，初始的时候所有能放士兵的地方都放了士兵的情况下，最多能删掉多少个士兵。

给每一行每一列分别建一个点，对于所有非障碍坐标(x,y)，从x行对应的点 向 y列对应的点连一条容量为1的边，表示这个位置的士兵最多可以删除一次。

源点向每一行对应的点连边，容量为这一行能删除的士兵个数的最大值（即 列数m - 这一行的障碍数 - 这一行需要的士兵数L[i]）。

每一列对应的点向汇点连边，容量为这一列能删除的士兵个数的最大值（即 行数n - 这一列的障碍数 - 这一列需要的士兵数C[i]）。

这样跑一个最大流，每一个单位的流量表示删除一个士兵，不难证明 任意一种流量状态都与一种合法的士兵删除方案相对应。

特判无解的情况，如果所有能放士兵的地方都放上了士兵，仍然存在行或列不满足限制条件，输出无解即可。

代码如下：

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

const int maxn = 2*100 + 7, inf = 0x7f7f7f7f;

namespace dinic {
	struct Edge {
		int to, res;
	};
	vector<int> G[maxn];
	vector<Edge> edges;
	inline void addedge(int f, int t, int c) {
		edges.push_back((Edge){t, c});
		edges.push_back((Edge){f, 0});
		int m = edges.size();
		G[f].push_back(m - 2);
		G[t].push_back(m - 1);
	}
	int vis[maxn], d[maxn], cur[maxn], s, t;
	bool bfs() {
		memset(vis, 0x00, sizeof(vis));
		queue<int> q; q.push(s); vis[s] = 1; d[s] = 0;
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = 0; i < G[x].size(); i ++) {
				Edge& e = edges[G[x][i]];
				if(e.res>0 && !vis[e.to]) {
					vis[e.to] = 1;
					d[e.to] = d[x] + 1;
					q.push(e.to);
				}
			}
		}
		return vis[t];
	}
	int dfs(int x, int a) {
		if(x==t || a==0) return a;
		int flow = 0, f;
		for(int& i = cur[x]; i < G[x].size(); i ++) {
			Edge& e = edges[G[x][i]];
			if(e.res>0 && d[e.to]==d[x]+1 && (f=dfs(e.to,min(a,e.res)))>0) {
				flow += f;
				a -= f;
				edges[G[x][i]^1].res += f;
				e.res -= f;
				if(a == 0) break;
			}
		}
		return flow;
	}
	int maxflow(int S, int T) {
		s=S;t=T; int flow = 0;
		while(bfs()) {
			memset(cur, 0x00, sizeof(cur));
			flow += dfs(s, inf);
		}
		return flow;
	}
}
using dinic::addedge;
using dinic::maxflow;

int m, n, k, L[maxn], C[maxn];
#define LX(x) (x)
#define LY(y) (m+(y))
#define ST    (n+m+1)
#define ED    (n+m+2)

int sol[maxn][maxn], iL[maxn], iC[maxn], acnt;

int main() {
	scanf("%d%d%d", &m, &n, &k); acnt = n*m;
	for(int i = 1; i <= m; i ++) scanf("%d", &L[i]);
	for(int i = 1; i <= n; i ++) scanf("%d", &C[i]);
	for(int i = 1; i <= k; i ++) {
		int x, y; scanf("%d%d", &x, &y);
		sol[x][y] = 1; iL[x] ++; iC[y] ++;
		acnt --;
	}
	for(int i = 1; i <= m; i ++) {
		for(int j = 1; j <= n; j ++)
			if(!sol[i][j]) addedge(LX(i), LY(j), 1);
	}
	for(int i = 1; i <= m; i ++) {
		int c = (n - iL[i]) - L[i];
		if(c < 0) {puts("JIONG!"); return 0;}
		addedge(ST, LX(i), c);
		//printf("[%3d] c = %3d iL = %3d L = %3d\n", i, c, iL[i], L[i]);
	}
	for(int i = 1; i <= n; i ++) {
		int c = (m - iC[i]) - C[i];
		if(c < 0) {puts("JIONG!"); return 0;}
		addedge(LY(i), ED, c);
		//printf("[%3d] c = %3d iC = %3d C = %3d\n", i, c, iC[i], C[i]);
	}
	int ans = acnt - maxflow(ST, ED);
	printf("%d\n", ans);
	return 0;
}