卡60分
查看原帖
卡60分
701221
Chr0n1CleC楼主2023/11/27 20:10
#include<cstdio>
#include<algorithm>
#include<queue>
#define f(i, j) ((i - 1) * m + j)
#define LL long long
using namespace std;

const int N = 100009;

struct node
{
	int v;
	LL w, c;
	int nxt;
}e[N * 100];

int head[N], cnt = 1, pre[N], vis[N], s, t, n, m;

LL dis[N], fl[N];

char str[29][29];

void add(int u, int v, LL w, LL c)
{
	e[++ cnt] = {v, w, c, head[u]}, head[u] = cnt;
}

void ADD(int u, int v, LL w, LL c)
{
	add(u, v, w, c), add(v, u, 0, -c);
}

bool bfs()
{
	for (int i = 0;i <= 2 * n * m + 1;++ i)
		dis[i] = fl[i] = 1e18, pre[i] = 0;
	dis[s] = 0;
	queue < int > q;
	q.push(s);
	while (!q.empty())
	{
		int u = q.front();
		q.pop(), vis[u] = 0;
		for (int i = head[u], v;i;i = e[i].nxt)
		{
			v = e[i].v;
			LL w = e[i].w, c = e[i].c;
			if (w && dis[v] > dis[u] + c)
			{
				dis[v] = dis[u] + c, fl[v] = min(fl[u], w), pre[v] = i;
				if (!vis[v])
					q.push(v), vis[v] = 1;
			}
		}
	}
	return pre[t];
}

int p[8][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};

int main()
{
	scanf("%d%d", &n, &m);
	t = 2 * n * m + 1;
	int sum1 = 0, sum2 = 0;
	for (int i = 1;i <= n;++ i)
	{
		scanf("%s", str[i] + 1);
		for (int j = 1;j <= m;++ j)
			if (str[i][j] - '0')
				++ sum1, ADD(s, f(i, j), 1, 0);
	}
	for (int i = 1;i <= n;++ i)
	{
		scanf("%s", str[i] + 1);
		for (int j = 1;j <= m;++ j)
			if (str[i][j] - '0')
				++ sum2, ADD(f(i, j) + n * m, t, 1, 0);
	}
	for (int i = 1;i <= n;++ i)
	{
		scanf("%s", str[i] + 1);
		for (int j = 1, x, y;j <= m;++ j)
		{
			x = str[i][j] - '0';
			ADD(f(i, j), f(i, j) + n * m, x, 0);
			for (int k = 0;k < 8;++ k)
			{
				x = i + p[k][0], y = j + p[k][1];
				if (x >= 1 && x <= n && y >= 1 && y <= m)
					ADD(f(i, j) + n * m, f(x, y), 1e9, 1);
			}
		}
	}
	if (sum1 != sum2)
	{
		printf("-1\n");
		return 0;
	}
	LL ans = 0;
	while (bfs())
	{
		sum1 -= fl[t], ans += fl[t] * dis[t];
		int cur = t, i;
		while (cur != s)
			i = pre[cur], e[i].w -= fl[t], e[i ^ 1].w += fl[t], cur = e[i ^ 1].v;
	}
	if (sum1)
		printf("-1\n");
	else
		printf("%lld\n", ans);
	
	return 0;
}
2023/11/27 20:10
加载中...