「雅礼集训 2018-03-25」cti

发表于

有一个n×mn\times m 的地图，地图上的每一个位置可以是空地，炮塔或是敌人。你需要操纵炮塔消灭敌人。

对于每个炮塔都有一个它可以瞄准的方向，你需要在它的瞄准方向上确定一个它的攻击位置，当然也可以不进行攻击。 一旦一个位置被攻击，则在这个位置上的所有敌人都会被消灭。保证对于任意一个炮塔，它所有可能的攻击位置上不存在另外一个炮塔。定义炮弹的运行轨迹为炮弹的起点和终点覆盖的区域。你需要求出一种方案，使得在没有两条炮弹轨迹相交的前提下，最大化消灭敌人的数量。

Constraints

$ 1 \leq n,m \leq 50 $

Solution

考虑对于每一个炮塔，将它们可以攻击的位置连成一条链。对于不能相交的限制，可以参考【bzoj3144】[Hnoi2013]切糕。

具体建图方式为：先将横着的链建好，再反着建竖着的链，最后在每一个相交点间连一条无穷大的边。

原理画图易得。

Code

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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=55;
const int M=2e5+5;
const int inf=0x3f3f3f3f;
int n,m,cnt=1,S,T,tot,ans,all;
int first[M],cur[M],map[N][N];
int q[M],dis[M];
int id[N][N],ord[N][N],chain[255][N];
struct edge{int to,next,flow;}e[M*4];
int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void ins(int u,int v,int w)
{
    e[++cnt]=(edge){v,first[u],w};first[u]=cnt;
    e[++cnt]=(edge){u,first[v],0};first[v]=cnt;
}
bool bfs()
{
    memset(dis,-1,sizeof(dis));
    int head=0,tail=1;q[0]=S;dis[S]=0;
    while(head!=tail)
    {
        int u=q[head++];
        for(int i=first[u];i;i=e[i].next)
        {
            int to=e[i].to;
            if(dis[to]!=-1||!e[i].flow)continue;
            dis[to]=dis[u]+1;
            q[tail++]=to;
        }
    }
    return dis[T]!=-1;
}
int dfs(int u,int a)
{
    if(u==T||a==0)return a;
    int f,flow=0;
    for(int& i=cur[u];i;i=e[i].next)
    {
        int to=e[i].to;
        if(dis[to]==dis[u]+1&&(f=dfs(to,min(e[i].flow,a)))>0)
        {
            e[i].flow-=f;e[i^1].flow+=f;
            flow+=f;a-=f;if(a==0)break;
        }
    }
    return flow;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            map[i][j]=read();
    S=++tot;T=++tot;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(map[i][j]==-1)
            {
                ins(++tot,T,1000);ans+=1000;
                int ccnt=0,tid=++all;
                chain[tid][++ccnt]=tot;
                for(int k=i-1;k>=1;k--)
                {
                    chain[tid][++ccnt]=++tot;
                    ins(tot,chain[tid][ccnt-1],1000-map[k][j]);
                    id[k][j]=tid;ord[k][j]=ccnt-1;
                }
                ins(S,tot,inf);
            }
            else if(map[i][j]==-2)
            {
                ins(++tot,T,1000);ans+=1000;
                int ccnt=0,tid=++all;
                chain[tid][++ccnt]=tot;
                for(int k=i+1;k<=n;k++)
                {
                    chain[tid][++ccnt]=++tot;
                    ins(tot,chain[tid][ccnt-1],1000-map[k][j]);
                    id[k][j]=tid;ord[k][j]=ccnt-1;
                }
                ins(S,tot,inf);
            }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(map[i][j]==-3)
            {
                ins(S,++tot,1000);ans+=1000;
                int last=tot;
                for(int k=j-1;k>=1;k--)
                {
                    ins(last,++tot,1000-map[i][k]);
                    if(id[i][k])ins(last,chain[id[i][k]][ord[i][k]],inf);
                    last=tot;
                }
                ins(tot,T,inf);
            }
            else if(map[i][j]==-4)
            {
                ins(S,++tot,1000);ans+=1000;
                int last=tot;
                for(int k=j+1;k<=m;k++)
                {
                    ins(last,++tot,1000-map[i][k]);
                    if(id[i][k])ins(last,chain[id[i][k]][ord[i][k]],inf);
                    last=tot;
                }
                ins(tot,T,inf);
            }
    while(bfs())
    {
        for(int i=1;i<=tot;i++)cur[i]=first[i];
        ans-=dfs(S,inf);
    }
    printf("%d",ans);
    return 0;
}