P2472 [SCOI2007]蜥蜴 (最大流)

题目

P2472 [SCOI2007]蜥蜴

解析

这个题思路比较清晰，本(qi)来(shi)以(jiu)为(shi)无脑建图跑最大流，结果挂了，整了一个小时后重新建图才过的。

建立一个超级源点和一个超级汇点，

每个石柱都有其固定的通过的次数，也就是说我们要限制其通过次数，怎么限制呢，拆点，把每个有石柱的点拆成两个，相连的边流量为其高度，这样就做到了限制其通过次数

对于\((i,j)\)位置

如果有石柱，连一条\((i,j)->(i,j)+n\times c\)，流量为石柱高度的边，来表示石柱可以通过几次
如果有蜥蜴，连一条\(s->(i,j)\)，流量为\(1\)的边，来表示这一只蜥蜴
如果有能到达的石柱\((x,y)\)，连一条\((i,j)+n\times c -> (x,y)\)，流量为\(INF\)的边
如果能出界，连一条\((i,j)->t\)的流量为\(INF\)的边

后两种情况的边只是起连接作用，所以流量为\(INF\).

注意：后面三条都是在满足第一条的条件下进行的。

通过上面的建图方法，我们就求出了可以出界的蜥蜴，然后我们用蜥蜴的总数\(-\)可以逃出的蜥蜴数就是最后的答案。

思路不难，就是建图麻烦的一批。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

const int INF = 0x3f3f3f3f;

int n, c, d, s, t, sum, num = 1;

int head[N], cur[N], dep[N];

int a[50][50];

char S[50];

class node {

	public :

		int v, nx, w;

} e[N];

template<class T>inline void read(T &x) {

	x = 0; int f = 0; char ch = getchar();

	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();

	x = f ? -x : x;

	return;

}

int bian_hao(int i, int j) {

	return (i - 1) * c + j;

}

inline void add(int u, int v, int w) {

	e[++num].nx = head[u], e[num].v = v, e[num].w = w, head[u] = num;

	e[++num].nx = head[v], e[num].v = u, e[num].w = 0, head[v] = num;

}

queue<int>q;

bool bfs() {

	memset(dep, 0, sizeof dep);

	memcpy(cur, head, sizeof cur);

	dep[s] = 1;

	q.push(s);

	while (!q.empty()) {

		int u = q.front();

		q.pop();

		for (int i = head[u]; ~i; i = e[i].nx) {

			int v = e[i].v;

			if (e[i].w && !dep[v]) dep[v] = dep[u] + 1, q.push(v);

		}

	}

	return dep[t];

}

int dfs(int u, int flow) {

	if (u == t) return flow;

	int use = 0;

	for (int &i = cur[u]; ~i; i = e[i].nx) {

		int v = e[i].v;

		if (e[i].w && dep[v] == dep[u] + 1) {

			int di = dfs(v, min(flow, e[i].w));

			e[i].w -= di, e[i ^ 1].w += di;

			use += di, flow -= di;

			if (flow <= 0) break;

		}

	}

	return use;

}

int dinic() {

	int ans = 0;

	while (bfs()) ans += dfs(s, INF);

	return ans;

}

int main() {

	memset(head, -1, sizeof head);

	read(n), read(c), read(d);

	s = (n * c) * 3 + 1, t = s + 1;

	for (int i = 1; i <= n; ++i) {

		scanf("%s", S + 1);

		for (int j = 1; j <= c; ++j) {

			a[i][j] = S[j] - '0';

			if (a[i][j]) {

				add(bian_hao(i, j), bian_hao(i, j) + n * c, a[i][j]);	//有石柱

				if (i <= d || i >= n - d + 1 || j <= d || j >= c - d + 1) add(bian_hao(i, j) + n * c, t, INF);	//可以出界

			}

		}

	}

	for (int i = 1; i <= n; ++i) {

		scanf("%s", S + 1);

		for (int j = 1; j <= c; ++j) if (S[j] == 'L')

			add(s, bian_hao(i, j), 1), sum++;			//有蜥蜴

	}

	for (int dx = -d; dx <= d; ++dx)

		for (int dy = -d; dy <= d; ++dy) {

			if (dx * dx + dy * dy > d * d) continue;

			for (int i = 1; i <= n; ++i)

				for (int j = 1; j <= c; ++j) {

					int x = i + dx, y = j + dy;

					if (x < 1 || x > n || y < 1 || y > c || !a[i][j]) continue;

					add(bian_hao(i, j) + n * c, bian_hao(x, y), INF);			//能到别的石柱

				}

		}

	printf("%d\n", sum - dinic());

}

巴特西

P2472 [SCOI2007]蜥蜴 (最大流)

题目

解析

代码

最新文章

热门文章