P1263 宫廷守卫

标准网络流建模

对于每一行,每一堵墙相当于把这行分成了很多部分

而每一列也是一样的qwq

然后我们发现一个空地代表了对应行的部分和对应列的部分只能放下一个兵

所以把对应行和列连边,表示如果这条边有流量这行和这列都不能有流量了

陷阱就相当于没有空地也不会增加新行划分列划分

所以最后建图就是行一排列一排s到行列到t类型的

输出方案的时候我们找这个二分图中间那些边即可qwq

做完了,其实建图和输出方案还是有一点难度的,但是没有细节啊

code:



#include<bits/stdc++.h>
#define mkp(x,y) (make_pair(x,y))
using namespace std;
const int MAXN = 500;
const int inf = 1e9 + 7;
const int MAXM = 2e5 + 7;
int m, n, ccnt, a[MAXN][MAXN], T, s, t, maxflow;
int nxt[MAXM], to[MAXM], home[MAXM], flw[MAXM], cur[MAXM];
int vis[MAXN][MAXN][2];
map<pair<int, int>, int> mp;

inline void cuntu(int x, int y, int z) {
	ccnt++;
	nxt[ccnt] = home[x];
	home[x] = ccnt;
	to[ccnt] = y;
	flw[ccnt] = z;
}

inline void ct(int x, int y, int z) {
	cuntu(x, y, z);
	cuntu(y, x, 0);
}

inline int GET(int x, int y, int p) {
	if(!vis[x][y][p])
		vis[x][y][p] = ++T;
	return vis[x][y][p];
}

int queh[MAXN], quel[MAXN];
inline void build() {
	ccnt = 1;
	for(int i = 1; i <= m; ++i) {
		// printf("H :%d\n", i);
		for(int j = 1; j <= n; ++j) {
			// printf("in L->%d ", j);
			if(a[i][j] == 2) {
				quel[j]++;//这一列点数+1
				queh[i]++;//这一行点数+1
				// printf("%d %d?\n", quel[j], queh[i]);
			} else if(a[i][j] == 0) {
				// printf("node :%d ct->node: %d?\n", GET(i, queh[i], 1), GET(j, quel[j], 0));
				ct(GET(i, queh[i], 1), GET(j, quel[j], 0), 1);
			}
		}
		// puts("");
	}
	++T;
	s = T;
	++T;
	t = T;
	for(int i = 1; i <= m; ++i) {
		for(int j = 0; j <= queh[i]; ++j) {
			// printf("s - >%d\n", GET(i, j, 1));
			ct(s, GET(i, j, 1), 1);
		}
	}
	for(int i = 1; i <= n; ++i) {
		for(int j = 0 ; j <= quel[i]; ++j) {
			// printf("t - > %d\n", GET(i, j, 0));
			ct(GET(i, j, 0), t, 1);
		}
	}
	return ;
}

inline void solve() {
	for(int u = 1; u <= T; ++u) {
		if(u == s || u == t)continue;
		bool flg = 0;
		for(int i = home[u]; i; i = nxt[i]) {
			int  v = to[i];
			if(v == s && flw[i] == 1)flg = 1;
			if(v == t && flw[i] == 0)flg = 2;//统计有没有流量
		}
		if(flg == 1) {//s出发有流量,说明这个点在匹配里
			for(int i = home[u]; i; i = nxt[i]) {
				int v = to[i];
				if(v != s && flw[i] == 0) {
					mp[mkp(min(u, v), max(u, v))] = 1; //这个点有了
					break;
				}
			}
		} else if(flg == 2) {
			for(int i = home[u]; i; i = nxt[i]) {
				int v = to[i];
				if(v != t && flw[i] == 1) {
					mp[mkp(min(u, v), max(u, v))] = 1;
					break;
				}
			}
		}
	}
	memset(quel, 0, sizeof(quel));
	memset(queh, 0, sizeof(queh));
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			if(a[i][j] == 2) {
				quel[j]++;
				queh[i]++;
			} else if(a[i][j] == 0) {
				int tmp1 = GET(i, queh[i], 1);
				int tmp2 = GET(j, quel[j], 0);
				if(tmp1 > tmp2)
					tmp1 ^= tmp2 ^= tmp1 ^= tmp2;
				if(mp.find(mkp(tmp1, tmp2)) != mp.end())
					printf("%d %d\n", i, j);
			}
		}
	}
	return ;
}

int h[MAXM];
int que[MAXM];
inline int bfs() {
	memset(h, 0, sizeof(h));
	int hd = 1, tl = 1;
	que[hd] = s;
	h[s] = 1;
	while(hd <= tl) {
		int u = que[hd];
		++hd;
		for(int i = home[u]; i; i = nxt[i]) {
			int v = to[i];
			if(!h[v] && flw[i] > 0) {
				h[v] = h[u] + 1;
				que[++tl] = v;
			}
		}
		if(h[t])return 1;
	}
	return h[t];
}

inline int dfs(int u, int nflw) {
	if(u == t || nflw == 0)return nflw;
	int ret = nflw, a = 0;
	for(int &i = cur[u]; i; i = nxt[i]) {
		int v = to[i];
		if(h[v] == h[u] + 1 && (a = dfs(v, min(ret, flw[i])))) {
			flw[i] -= a;
			flw[i ^ 1] += a;
			ret -= a;
			if(!ret)break;
		}
	}
	if(nflw == ret)h[u] = -1;
	return (nflw - ret);
}

inline void Dinic() {
	maxflow = 0;
	while(bfs()) {
		memcpy(cur, home, sizeof(cur));
		maxflow += dfs(s, inf);
	}
	printf("%d\n", maxflow);
	solve();
	return ;
}

int main() {
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= m; ++i) {
		for(int j = 1; j <= n; ++j) {
			scanf("%d", &a[i][j]);
		}
	}
	build();//建图
	Dinic();
	return 0;
}

别看长其实和昨天的DP比起来可好写了差老多了

夏晓光(loveJY)的博客

P4099 [HEOI2013]SAO