洛谷 2472 [SCOI2007]蜥蜴 题解

发表于 | 阅读次数：
本文字数： 1.3k 字 | 阅读时长 ≈ 6 分钟

题意简述

(这题超套路…)
有一个 $n\times m$ 的矩阵，其中一些位置上有蜥蜴。每个位置上有一个石柱，给你他们初始的高度 $a_{i,j}$。一个蜥蜴可以从一个石柱，跳到直线距离 $\le k$ 的另一个石柱上。当一只蜥蜴从一个石柱上离开的时候，这个石柱的高度就会减少 $1$ 。如果蜥蜴跳到了矩阵外面，就是逃离了。请你求最少有多少只不能逃离（其实就是最多能逃离几只）。

$1<=n,m<=20$，$k<=4$。

【附】直线距离：从 $(x1,y1)$ 到 $(x2,y2)$ 的直线距离为： $\sqrt{(x1-x2)^2+(y1-y2)^2}$

思路框架

显然建网络流。首先我们把矩阵展开，就是把 $(i,j)$ 位置的点编号为 $(i-1)m+j$。

每个石柱上只能通过定量的蜥蜴，这显然是一个点限流。套路拆点，每个位置变成 $In(i,j)$ 和 $Out(i,j)$。设源点为 $S$ ，汇点为 $T$。

对于每个点 $(i,j)$：

$In(i,j) \xrightarrow[a_{i,j}]{} Out(i,j)$ （一个石柱上只能通过 $a_{i,j}$ 个蜥蜴）
$S \xrightarrow[1]{} In(i,j)$ （一个石柱上只能有一个蜥蜴）
$Out(i,j) \xrightarrow[inf]{} T$ （跳出终点就随便了）

对于点 $(i,j)$ 和点 $(u,v)$ 满足 $(i,j)$ 到 $(u,v)$ 直线距离 $\le k$：
$Out(i,j) \xrightarrow[inf]{} In(u,v)$ （点之间跳是不限的）
$Out(u,v) \xrightarrow[inf]{} In(i,j)$

这样跑一个最大流即珂。

Q：为什么点到点，点到 $T$ 之间都是 $inf$ 的边呢？怎么就“随便”了？
A：其实并不是随便，我们知道，网络流上一个流能流过的值是其路径上的最小值。那么既然 $In(i,j)$ 到 $Out(i,j)$ 的时候，已经限过了一次 $a_{i,j}$ ，那我们从 $Out(i,j)$ 到 $In(u,v)$ 的时候，再限一次也没有必要了。当然，你如果实在要限这条边流量为 $a_{i,j}$，没有任何问题。

代码

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
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1333
    #define INF 0x3f3f3f3f
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }
    class Graph //这些是板子
    {
    public:
        int EdgeCount;
        int head[N];
        struct Edge
        {
            int To,Label;
            int Next;
        }Ed[200100];
        void clear()
        {
            MEM(head,-1);
            MEM(Ed,-1);
            EdgeCount=-1;
        }
        void AddEdge(int u,int v,int w)
        {
            ++EdgeCount;
            Ed[EdgeCount]=(Edge){v,w,head[u]};
            head[u]=EdgeCount;
        }
        void AddFlow(int u,int v,int w)
        {
            AddEdge(u,v,w);
            AddEdge(v,u,0);
        }

        int Source,Sink;
        int deep[N];
        queue<int>Q,EmptyQ;
        bool BFS()
        {
            Q=EmptyQ;
            FK(deep);

            Q.push(Source);
            deep[Source]=1;
            do
            {
                int u=Q.front();Q.pop();
                for(int i=head[u];~i;i=Ed[i].Next)
                {
                    int v=Ed[i].To;
                    if (deep[v]==0 and Ed[i].Label>0)
                    {
                        deep[v]=deep[u]+1;
                        Q.push(v);
                    }
                }
            }while(!Q.empty());

            if (deep[Sink]==0) return 0;
            return 1;
        }
        int DFS(int u,int MinFlow)
        {
            if (u==Sink) return MinFlow;
            for(int i=head[u];~i;i=Ed[i].Next)
            {
                int v=Ed[i].To;
                if (deep[v]==deep[u]+1 and Ed[i].Label!=0)
                {
                    int d=DFS(v,min(MinFlow,Ed[i].Label));
                    if (d>0)
                    {
                        Ed[i].Label-=d;
                        Ed[i^1].Label+=d;
                        return d;
                    }
                }
            }
            return 0;
        }
        int Dinic()
        {
            int ans=0;
            while(BFS())
            {
                int d;
                while(d=DFS(Source,0x3f3f3f3f))
                {
                    ans+=d;
                }
            }
            return ans;
        }
    }Nt;
    #define S Nt.Source
    #define T Nt.Sink
    #define id(i,j,x) (x*n*m+(i-1)*m+j)
    //(x,y,0): In
    //(x,y,1): Out

    int n,m,k; int cnt;
    int a[N][N]; char t[N];
    void Input()
    {
        Rd(3,&n,&m,&k);
        F(i,1,n) F(j,1,m) scanf("%1d",&a[i][j]);
        Nt.clear();
        S=2*n*m+1,T=2*n*m+2;
        F(i,1,n)
        {
            scanf("%s",t+1);
            F(j,1,m) if (t[j]=='L' and a[i][j]>0) 
           //如果一开始石柱就没了，我们就忽略这个蜥蜴
            {
                ++cnt;
                Nt.AddFlow(S,id(i,j,0),1); 
            }
        }
    }

    void Soviet()
    {
        F(i,1,n) F(j,1,m)     Nt.AddFlow(id(i,j,0),id(i,j,1),a[i][j]);
        //建In(i,j)到Out(i,j)的边
        F(i,1,n) F(j,1,m) if (i-k<1 or j-k<1 or i+k>n or j+k>m)
        {
            Nt.AddFlow(id(i,j,1),T,INF);
           //建立到终点的边
        }
        F(i,1,n) F(j,1,m) F(u,max(i-k,1),min(i+k,n)) F(v,max(j-k,1),min(j+k,m)) if (a[i][j] and a[u][v])
        {
            if (i==u and v==j) continue;
            if ((i-u)*(i-u)+(j-v)*(j-v)<=k*k)
           //直线距离<=k
            {
                Nt.AddFlow(id(i,j,1),id(u,v,0),INF);
                Nt.AddFlow(id(u,v,1),id(i,j,0),INF);
              //建边
            }
        }
        printf("%d\n",cnt-Nt.Dinic());
       //蜥蜴的数量-最大的能逃脱的数量，就是最少的不能逃脱的数量
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}
w