\(\text{Solution}\)

一眼不会，限制有点多。。。

那就网络流

发下确实是很简单的建图

枚举起点集合

拆点后就很好满足限制了
\(\text{Code}\)

#include <cstdio>

#include <iostream>

#include <cstring>

#define RE register

#define IN inline

using namespace std;

const int N = 1005, INF = 2147483647;

int n, m, S, T, num, p1, p2, tot, ans;

int dis[N], h[N], vis[N], pre[N], edge[N], flow[N], a[25][25], d[N], buc[N], Q[N];

int fx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

char str[20];

struct node{int to, nxt, w, f;}e[N * 10];

IN void add(int u, int v, int w, int f)

{

	e[++tot] = node{v, h[u], w, f}, h[u] = tot;

	e[++tot] = node{u, h[v], 0, -f}, h[v] = tot;

}

IN int Isin(int x, int y){return (x > 0 && x <= n && y > 0 && y <= m && a[x][y] != 101);}

IN int getid(int x, int y){return (x - 1) * m + y;}

IN int spfa()

{

	for(RE int i = S; i <= T; i++) vis[i] = 0, dis[i] = flow[i] = INF;

	int head = 0, tail = 1;

	d[1] = S, vis[S] = 1, dis[S] = 0, pre[T] = -1;

	while (head < tail)

	{

		int now = d[++head];

		vis[now] = 0;

		for(RE int i = h[now]; i; i = e[i].nxt)

		if (dis[e[i].to] > dis[now] + e[i].f && e[i].w)

		{

			dis[e[i].to] = dis[now] + e[i].f, flow[e[i].to] = min(flow[now], e[i].w), pre[e[i].to] = now, edge[e[i].to] = i;

			if (!vis[e[i].to]) vis[e[i].to] = 1, d[++tail] = e[i].to;

		}

	}

	return pre[T] != -1;

}

IN int MCMF()

{

	int now, Maxflow = 0, Mincost = 0;

	while (spfa())

	{

		Maxflow += flow[T], Mincost += dis[T] * flow[T], now = T;

		while (now != S) e[edge[now]].w -= flow[T], e[edge[now] ^ 1].w += flow[T], now = pre[now];

	}

	if (Maxflow != num / 2) return INF;

	return Mincost;

}

IN void solve()

{

	memset(h, 0, sizeof h), tot = 1, T = n * m * 2 + 1;

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

		for(RE int j = 1; j <= m; j++)

		if (a[i][j] != 101)

		{

			if (a[i][j] == 100) add(getid(i, j), getid(i, j) + n * m, 1, 1);

			else add(getid(i, j), getid(i, j) + n * m, 1, 0);

			for(RE int k = 0; k < 4; k++)

			{

				int x = i + fx[k][0], y = j + fx[k][1];

				if (Isin(x, y)) add(getid(i, j) + n * m, getid(x, y), 1, 0);

			}

		}

	for(RE int i = 1; i <= num; i++)

		if (buc[Q[i]]) add(S, Q[i], 1, 0);

		else add(Q[i] + n * m, T, 1, 0);

	ans = min(ans, MCMF());

}

void dfs(int x, int s)

{

	if (s > num / 2) return;

	if (x > num)

	{

		if (s == num / 2 && ((!p1 && !p2) || (buc[p1] && buc[p2]))) solve();

		return;

	}

	buc[Q[x]] = 1, dfs(x + 1, s + 1), buc[Q[x]] = 0, dfs(x + 1, s);

}

int main()

{

	int q; scanf("%d", &q);

	for(; q; --q)

	{

		memset(buc, 0, sizeof buc), num = p1 = p2 = 0, ans = INF, scanf("%d%d", &n, &m);

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

		{

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

			for(RE int j = 1, id; j <= m; j++)

				if (str[j] == '.') a[i][j] = 100;

				else if (str[j] == '#') a[i][j] = 101;

				else

				{

					a[i][j] = str[j] - 'A' + 1, id = getid(i, j), Q[++num] = id;

					if (buc[a[i][j]]) p1 = buc[a[i][j]], p2 = id;

					buc[a[i][j]] = id;

				}

		}

		memset(buc, 0, sizeof buc), dfs(1, 0), printf("%d\n", (ans == INF ? -1 : ans));

	}

}
巴特西

JZOJ 3281. 【GDOI2013】字母连接

\(\text{Solution}\)

\(\text{Code}\)

最新文章

热门文章
