GMOJ S5057 【炮塔】

Description

有一个 $n \times m$ 的地图, 地图上的每一个位置可以是炮塔或是敌人。你需要操纵炮塔消灭敌人。炮塔有方向，定义炮弹的运行轨迹为炮弹的起点和打击点（一个炮塔最多只能有一个打击点）之间的路径。问你在没有两条炮弹轨迹相交的情况下，打到的敌人总数最多是多少。

$$1 \leq n; m \leq 50$$

Solution

妙。

主要考虑如何解决轨迹不能相交。

注意到若无视方向，则相交的轨迹实际上给出了一条炮塔之间的路径。

那么我们强制规定这些路径都是从纵向炮塔走向横向炮塔的，那么对于横向炮塔，将其射出的线方向置反，但能射到的点不变（即并非改变炮塔的方向，而是改变射线的方向），对于纵向的炮塔就不用管它了。

轨迹不相交就是相当于不存在这样的一条路径，即一个割，于是我们就可以考虑用 最小割 来求解了。

于是现在的重点就转变为了如何给每条边确定容量。

首先我们先规定，如果我们割了一条点 $u$ 到点 $v$ 的边，则表示我们选择攻击了 $u$ 这个格子，那么就可以对于一条路径上的边（不考虑是否与其他炮塔的路径相交），连一条从点 $u$ 到点 $v$，容量为这个炮塔能打到的最大的敌人数 - 这个点上的敌人数的边了。

于是我们可以考虑求出割每一条边的代价。

显然为：一个炮塔能打到的最大的敌人数 - 点 $u$ 这个格子上的敌人数。

于是答案等于：所有炮塔能打到的最大的敌人数的和 - 最小割，又因为最小割 = 最大流，所以答案就是：所有炮塔能打到的最大的敌人数的和 - 最大流。

但是这个做法是错误的，因为我们要限制路径不能转多次向，不然就可能会把一个合法的方案给判成不合法，于是我们可以想到把一个点拆成横向点和纵向点两个点，让纵向点向横向点连边，这样就可以强制最多只能够转一次向了。

然后就是原点向所有纵向炮塔连边，横向炮塔向汇点连边，容量均为正无穷。

时间复杂度为 $O(\text{maxflow}(n \times m, n \times m))$。

部分内容整理自 官方题解 和网络题解。

Code

#include <cstdio>
#include <cstring>
#define maxN 60
#define inf 2147483647
struct edge{ int x, y, c, g; } b[(maxN * maxN) << 5];
int len = 1, n = 0, m = 0, S = 0, T = 0;
int a[maxN][maxN];
int dep[maxN * maxN * 2], f[maxN * maxN * 2], h[maxN * maxN * 2];
int min (int x, int y)
{
	return x < y ? x : y;
}
int max (int x, int y)
{
	return x > y ? x : y;
}
int calc (int x, int y, int k)
{
	return ((x - 1) * m + y) + (k * n * m);
}
void ins (int x, int y, int c)
{
	len++;
	b[len].x = x;
	b[len].y = y;
	b[len].c = c;
	b[len].g = h[x];
	h[x] = len;
	
	len++;
	b[len].x = y;
	b[len].y = x;
	b[len].c = 0;
	b[len].g = h[y];
	h[y] = len;
}
bool bfs ()
{
	int tou = 1, wei = 2;
	f[1] = S;
	dep[S] = 1;
	while(tou < wei)
	{
		int x = f[tou];
		for(register int i = h[x];i;i = b[i].g)
		{
			int y = b[i].y;
			if(b[i].c && !dep[y])
			{
				dep[y] = dep[x] + 1;
				f[wei] = y;
				wei++;
				if(y == T)
				{
					return true;
				}
			}
		}
		tou++;
	}
	return false;
}
int dfs (int x, int flow)
{
	if(x == T)
	{
		return flow;
	}
	int now = flow;
	for(register int i = h[x];i;i = b[i].g)
	{
		int y = b[i].y;
		if(b[i].c && dep[y] == dep[x] + 1)
		{
			int ma = min(now, b[i].c);
			now -= ma;
			b[i].c -= ma;
			b[i ^ 1].c += ma;
			int rest = ma - dfs(y, ma);
			now += rest;
			b[i].c += rest;
			b[i ^ 1].c -= rest;
		}
	}
	return flow - now;
}
int main ()
{
	freopen("tower.in", "r", stdin);
	freopen("tower.out", "w", stdout);
	int Ans = 0;
	scanf("%d %d", &n, &m);
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= m; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	S = 0, T = 2 * n * m + 1;
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= m; j++)
		{
			if(a[i][j] < 0)
			{
				if(a[i][j] == -1)
				{
					int Ma = 0;
					for(int k = 1;k <= i; k++)
					{
						Ma = max(Ma, a[k][j]);
					}
					Ans += Ma;
					for(int k = i;k > 1; k--)
					{
						ins(calc(k, j, 0), calc(k - 1, j, 0), Ma - max(a[k][j], 0));
					}
					ins(S, calc(i, j, 0), inf);
				}
				else if(a[i][j] == -2)
				{
					int Ma = 0;
					for(int k = i;k <= n; k++)
					{
						Ma = max(Ma, a[k][j]);
					}
					Ans += Ma;
					for(int k = i;k < n; k++)
					{
						ins(calc(k, j, 0), calc(k + 1, j, 0), Ma - max(a[k][j], 0));
					}
					ins(S, calc(i, j, 0), inf);
				}
				else if(a[i][j] == -3)
				{
					int Ma = 0;
					for(int k = 1;k <= j; k++)
					{
						Ma = max(Ma, a[i][k]);
					}
					Ans += Ma;
					for(int k = 1;k < j; k++)
					{
						ins(calc(i, k, 1), calc(i, k + 1, 1), Ma - max(a[i][k + 1], 0));
					}
					ins(calc(i, j, 1), T, inf);
				}
				else
				{
					int Ma = 0;
					for(int k = j;k <= m; k++)
					{
						Ma = max(Ma, a[i][k]);
					}
					Ans += Ma;
					for(int k = m;k > j; k--)
					{
						ins(calc(i, k, 1), calc(i, k - 1, 1), Ma - max(a[i][k - 1], 0));
					}
					ins(calc(i, j, 1), T, inf);
				}
			}
		}
	}
	for(int i = 1;i <= n; i++)
	{
		for(int j = 1;j <= m; j++)
		{
			ins(calc(i, j, 0), calc(i, j, 1), inf);
		}
	}
	while(bfs())
	{
		Ans -= dfs(S, inf);
		memset(dep, 0, sizeof(dep));
	}
	printf("%d", Ans);
	return 0;
}