BZOJ4657 Tower

题意

有一个 $n \times m$ 的地图,地图上的每一个位置可以是空地,炮塔或是敌人。你需要操纵炮塔消灭敌人。
对于每个炮塔都有一个它可以瞄准的方向,你需要在它的瞄准方向上确定一个它的攻击位置,当然也可以不进行攻击。一旦一个位置被攻击,则在这个位置上的所有敌人都会被消灭。
保证对于任意一个炮塔,它所有可能的攻击位置上不存在另外一个炮塔。
定义炮弹的运行轨迹为炮弹的起点和终点覆盖的区域。你需要求出一种方案,使得没有两条炮弹轨迹相交。
$1 \le n,m \le 50$。

题解

像这种做起来不那么简单,范围相对比较小的题,都可以想到网络流。个人觉得这个建边的思路可以说很神奇了。
首先不考虑炮弹轨迹相交的限制,那么对于每个炮弹贪心取最大就可以了。但是炮弹轨迹不可相交,于是我们考虑类似退流的一种操作。
先将每个点拆成两个点。对于上下的炮塔,将原点与炮塔连一条流量为INF的边。对于左右的炮塔,将炮塔与汇点连一条INF的边。对于每个点拆成的两个点,两个点之间连一条流量为INF的边。对于每个上下的炮塔,则一直向炮塔所攻击的方向连边。连边的边权为这个炮塔所能打到的最多的敌人数与这条边的起点处的敌人数之差。对于每个左右的炮塔,则由炮塔所能打到的敌人最多的地方开始向炮塔连边,连边的边权为敌人最多的地方与这条边终点处的敌人数之差。考虑这么连边的意义,可以从最小割的角度思考。对于上下的炮塔,割掉某条边,会造成炮塔只能打到这条边的起点,也就会造成所割掉的边权的损失。对于左右的炮塔,割掉某条边,会导致炮塔只能打到这条边的终点,同样会造成边权大小的损失。而最后最小割之后图中没有了流量,也就意味着炮塔的攻击路线没有相交了。
时间复杂度$O(maxflow(n^2,n^2))$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=50+10;
const int maxm=2e6+10;
int a[maxn][maxn],to[maxm],nex[maxm],beg[maxm],flow[maxm],gap[maxm],dis[maxm];
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int s,t,n,m,node,e;
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline void add(int x,int y,int z){
to[++e]=y;nex[e]=beg[x];beg[x]=e;flow[e]=z;
to[++e]=x;nex[e]=beg[y];beg[y]=e;flow[e]=0;
}
inline int encode(int x,int y,int lvl){
return (x-1)*m+y+lvl*n*m;
}
inline bool chk(int x,int y){
return x>=1 && y>=1 && x<=n && y<=m;
}
int Isap(int x,int f){
if(x==t)return f;
int i,res=f;
for(i=beg[x];i;i=nex[i])
if(flow[i] && dis[x]==dis[to[i]]+1){
int minflow=Isap(to[i],min(res,flow[i]));
flow[i]-=minflow;
flow[i^1]+=minflow;
res-=minflow;
if(!res)return f;
}
if(!(--gap[dis[x]]))dis[s]=node;
gap[++dis[x]]++;
return f-res;
}
int main(){
int i,j;
#ifndef ONLINE_JUDGE
freopen("cti.in","r",stdin);
freopen("cti.out","w",stdout);
#endif
n=read();m=read();
s=2*n*m+1,node=t=2*n*m+2;e=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
a[i][j]=read();
int Maxval=1e6+10;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if(a[i][j]>=-2 && a[i][j]<=-1)add(s,encode(i,j,0),Maxval);
if(a[i][j]>=-4 && a[i][j]<=-3)add(encode(i,j,1),t,Maxval);
}
int ans=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
if(a[i][j]>=0)continue;
int x=i,y=j,D=abs(a[i][j])-1,Max=0;
for(;chk(x,y);x+=dir[D][0],y+=dir[D][1])Max=max(Max,a[x][y]);
ans+=Max;x=i;y=j;
if(a[i][j]>=-2 && a[i][j]<=-1)
for(;chk(x+dir[D][0],y+dir[D][1]) && a[x][y]<Max;x+=dir[D][0],y+=dir[D][1])
add(encode(x,y,0),encode(x+dir[D][0],y+dir[D][1],0),Max-max(0,a[x][y]));
if(a[i][j]>=-4 && a[i][j]<=-3)
for(;chk(x+dir[D][0],y+dir[D][1]) && a[x][y]<Max;x+=dir[D][0],y+=dir[D][1])
add(encode(x+dir[D][0],y+dir[D][1],1),encode(x,y,1),Max-max(0,a[x][y]));
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
add(encode(i,j,0),encode(i,j,1),Maxval);
for(gap[0]=node;dis[s]<node;)ans-=Isap(s,INF);
printf("%d\n",ans);
return 0;
}