Wa 45pts球条
查看原帖
Wa 45pts球条
1046406
Unpt_V3楼主2025/1/22 09:25
#include <bits/stdc++.h>

using namespace std;

const int N = 3e4 + 5, M = 100 * N;
int n, m, k, r, c, tot = 1, head[N], now[N], dis[N], s, t, tg[55][55], x[55], y[55];
int dx[] = {0, 0, 0, 0}, dy[] = {0, 0, 0, 0};
bool vis[N];
char mp[55][55], ch;
queue<int> q;

struct node {
	int to, nxt, w;
} e[2 * M];

void Add(int u, int v, int w) {
	e[++tot] = {v, head[u], w};
	head[u] = tot;
}

void add(int u, int v, int w) {
	Add(u, v, w), Add(v, u, 0);
}

bool spfa() {
	memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0, now[s] = head[s], vis[s] = true;
	q.push(s);
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		now[u] = head[u];
		vis[u] = false;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to, w = e[i].w;
			now[v] = head[v];
			if (!w) continue;
			if (dis[v] > dis[u] + 1) {
				dis[v] = dis[u] + 1;
				if (!vis[v]) vis[v] = true, q.push(v);
			}
		}
	}
	return dis[t] != dis[t + 1];
}

int dfs(int u, int mxf) {
	if (u == t || !mxf) return mxf;
	int res = 0;
	for (int i = now[u]; i; i = e[i].nxt) {
		int v = e[i].to, w = e[i].w;
		now[u] = i;
		if (!w) continue;
		if (dis[v] == dis[u] + 1) {
			int f = dfs(v, min(mxf, w));
			if (!f) dis[v] = 0;
			mxf -= f, e[i].w -= f, e[i ^ 1].w += f;
			res += f;
			if (!mxf) break;
		}
	}
	return res;
}

int dinic() {
	int ans = 0;
	while (spfa()) ans += dfs(s, 1e9);
	return ans;
}

int main() {
	cin >> m >> n >> r >> c;
	dx[0] = -r, dx[1] = -c, dx[2] = c, dx[3] = r;
	dy[0] = c, dy[1] = r, dy[2] = r, dy[3] = c;
	s = N - 10, t = s + 1;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++) {
			cin >> ch;
			mp[i][j] = ch;
			if (ch == '.') {
				k++;
				tg[i][j] = k;
				x[k] = i, y[k] = j;
				add(s, k, 1), add(k + n * m, t, 1);
			}
		}
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j < 4; j++) {
			int tx = x[i] + dx[j], ty = y[i] + dy[j];
			if (tx >= 1 && tx <= m && ty >= 1 && ty <= n && mp[tx][ty] == '.') {
				add(i, tg[tx][ty] + n * m, 1);
			}
		}
	}
	cout << k - dinic();
	return 0;
}
2025/1/22 09:25
加载中...