BZOJ 1066 [SCOI2007]蜥蜴 模組化+網絡流

Description

　　在一個r行c列的網格地圖中有一些高度不同的石柱，一些石柱上站着一些蜥蜴，你的任務是讓盡量多的蜥蜴逃

到邊界外。 每行每列中相鄰石柱的距離為1，蜥蜴的跳躍距離是d，即蜥蜴可以跳到平面距離不超過d的任何一個石

柱上。石柱都不穩定，每次當蜥蜴跳躍時，所離開的石柱高度減1（如果仍然落在地圖内部，則到達的石柱高度不

變），如果該石柱原來高度為1，則蜥蜴離開後消失。以後其他蜥蜴不能落腳。任何時刻不能有兩隻蜥蜴在同一個

石柱上。

Input

　　輸入第一行為三個整數r，c，d，即地圖的規模與最大跳躍距離。以下r行為石竹的初始狀态，0表示沒有石柱

，1~3表示石柱的初始高度。以下r行為蜥蜴位置，“L”表示蜥蜴，“.”表示沒有蜥蜴。

Output

　　輸出僅一行，包含一個整數，即無法逃離的蜥蜴總數的最小值。

Sample Input

5 8 2

00000000

02000000

00321100

02000000

00000000

........

........

..LLLL..

........

........

Sample Output

1

HINT

100%的資料滿足：1<=r, c<=20, 1<=d<=4

Source

​​題目連結​​

這題作為網絡流的入門題目還是可以的。

此題就是一道模組化題。

首先說一下距離d不是曼哈頓距離。。。是歐拉距離。。。勾股那個。

此題的思想很簡單，裂點，一個高度為x的石柱可以看成編号i->j，其中C(i,j)=x。

那麼對于第(i,j)個石柱如何裂呢？如果說i從1開始計算，j從0開始，那麼

now=r*2*(i-1)+2*j，

然後這個點可以分為“出點”和“入點”，分别是now+1和now+2。

所有其他點和它相連時，now+1連向别的點，别的點連向now+2.

最後建立一個超級源節點s和超級彙節點t。

s連向所有L處的入點，所有

能夠通過距離d跳到格子外部的出點連向t。

是以空間我們要開r*c*2+2.

接下來就是跑最大流的過程……

ISAP裡面gap優化總是要漏一句。。。我說怎麼TLE了呢。。

開的空間注意一下，，特别是邊數等等。

我Map（輸入數組）的空間開大了一點點，防止資料不好導緻我查不出錯。。。

代碼有點長，有點醜

建圖有點難受，，不過其實雖然長但是看起來應該挺好懂的吧。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int 
    MAX=200,
    inf=10,
    VerMax=2000,
    EdgMax=10000;
int r,c,dd,Ecnt,sumxy,Ver;
int source,sink;
int cur[VerMax],pre[VerMax],d[VerMax];
int Q[EdgMax],gap[EdgMax];
int Map[MAX][MAX];
struct Edge{
    int next,to,C;
}E[2000000];int head[VerMax];
int dist(int x,int y){
    return x*x+y*y;
}
int vertexb(int i,int j){
    return r*2*(i-1)+2*j;
}
void add(int u,int v,int w){
    E[Ecnt].next=head[u];
    E[Ecnt].to=v;
    E[Ecnt].C=w;
    head[u]=Ecnt++;
}
bool out(int x,int y){
    y++;
    for (int i=0;i<=c;i++)
        if (dist(0-x,i-y)<=dd*dd) return 1;
    for (int i=0;i<=r;i++)
        if (dist(0-y,i-x)<=dd*dd) return 1;
    for (int i=1;i<=c+1;i++)
        if (dist(r+1-x,i-y)<=dd*dd) return 1;
    for (int i=1;i<=r+1;i++)
        if (dist(c+1-y,i-x)<=dd*dd) return 1;
    return 0;
}
void build(){
    char tmp[MAX]; Ecnt=0;
    memset(head,255,sizeof(head));
    for (int i=1;i<=r;i++)
        for (int j=0;j<c;j++)
            if (Map[i][j]){
                int now=vertexb(i,j);
                add(now+2,now+1,Map[i][j]);
                add(now+1,now+2,0);
            }
    for (int i=1;i<=r;i++)
        for (int j=0;j<c;j++){
            if (!Map[i][j]) continue;
            int nowb=vertexb(i,j),now;
            for (int x=1;x<=r;x++)
                for (int y=0;y<c;y++)
                    if (Map[x][y] && (x!=i || y!=j))
                        if (dist(x-i,y-j)<=dd*dd){
                            now=vertexb(x,y);
                            add(nowb+1,now+2,inf);
                            add(now+2,nowb+1,0);
                            add(now+1,nowb+2,inf);
                            add(nowb+2,now+1,0);
                        }
        }
    sumxy=0;
    int Max=vertexb(r,c-1)+2;
    for (int i=1;i<=r;i++){
        scanf("%s",tmp);
        for (int j=0;j<c;j++)
            if (tmp[j]=='L'){
                sumxy++;
                int now=vertexb(i,j);
                add(Max+1,now+2,1);
                add(now+2,Max+1,0);
            }
    }
    for (int i=1;i<=r;i++)
        for (int j=0;j<c;j++)
            if (Map[i][j] && out(i,j)){
                int now=vertexb(i,j);
                add(now+1,Max+2,inf);
                add(Max+2,now+1,0);
            }
    source=Max+1;
    sink=Max+2;
}
void BFS(){
    memset(gap,0,sizeof(gap));
    memset(d,255,sizeof(d));
    gap[0]=1; d[sink]=0;
    int Head=0,tail=1;
    Q[0]=sink;
    while (Head!=tail){
        int u=Q[Head++];
        for (int i=head[u];~i;i=E[i].next){
            int j=E[i].to;
            if (~d[j]) continue;
            d[j]=d[u]+1;
            gap[d[j]]++;
            Q[tail++]=j;
        }
    }
}
int ISAP(){
    BFS();
    memcpy(cur,head,sizeof(cur));
    int u,flow=0;
    u=pre[source]=source;
    while (d[sink]<Ver+1){
        if (u==sink){
            int f=inf,neck;
            for (int i=source;i!=sink;i=E[cur[i]].to)
                if (f>E[cur[i]].C)
                    neck=i,f=E[cur[i]].C;
            for (int i=source;i!=sink;i=E[cur[i]].to)
                E[cur[i]].C-=f,E[cur[i]^1].C+=f;
            flow+=f;
            u=neck;
        }
        int j;
        for (j=cur[u];~j;j=E[j].next)
            if (E[j].C && d[E[j].to]+1==d[u]) break;
        if (~j){
            cur[u]=j;
            pre[E[j].to]=u;
            u=E[j].to;
        }    else{
            if (!(--gap[d[u]])) break;
            int mind=Ver+1;
            for (int i=head[u];~i;i=E[i].next)
                if (E[i].C && mind>d[E[i].to])
                    cur[u]=i,mind=d[E[i].to];
            d[u]=mind+1;
            gap[d[u]]++;
            u=pre[u];
        }
    }
    return flow;
}
int main(){
    r=read(),c=read(),dd=read();
    char tmp[MAX];
    Ver=0;
    for (int i=1;i<=r;i++){
        scanf("%s",tmp);
        for (int j=0;j<c;j++){
            Map[i][j]=tmp[j]-48;
            if (Map[i][j]) Ver++;
        }
    }
    Ver*=2; Ver+=2;
    build();
    printf("%d\n",sumxy-ISAP());
}