BZOJ1066_蜥蜴

题目传送门

经过长时间的旅行，很长时间没写过博客了，这次把上次WA的题目过了。

由于每次蜥蜴从石柱上跳下时，石柱的高度会-1，可以看做占了一格的流量。

建图：

　　1.建超级源和超级汇，设超级源连到每只蜥蜴的边容量为1，每个可以跳到外面的点连到超级汇的边的容量为maxlongint。

　　2.对于每个点建一个虚点，连边到此虚点，边容量为该点石柱高度。对于每个可以互相跳到的点，建立容量为maxlongint的边。这样当前点到其他点的总容量为该点的石柱高度。（拆点）

然后跑一遍Dinic就好了。

注意用蜥蜴的总数减去最大流才是答案。

code：

/**************************************************************

    Problem: 1066

    User: yekehe

    Language: C++

    Result: Accepted

    Time:40 ms

    Memory:6380 kb

****************************************************************/

#include <cstdio>

#include <string>

#include <cstring>

#include <iostream>

using namespace std;

int r,c,d,a[][],L;

string S;

int head[],nxt[],W[],To[],cnt;

void add(int x,int y,int c)

{

    W[cnt]=c;

    To[cnt]=y;

    nxt[cnt]=head[x];

    head[x]=cnt;

    cnt++;

}

int check(int x,int y,int fx,int fy)

{

    return (x-fx)*(x-fx)+(y-fy)*(y-fy)<=d*d;

}

int l[],dist[];

int BFS()

{

    int tl=,hd=;

    hd=tl=;

    l[++tl]=;

    memset(dist,-,sizeof dist);

    dist[]=;

        while(hd<tl){

            int front=l[++hd];

                for(int i=head[front];i!=-;i=nxt[i]){

                    if(dist[To[i]]==- && W[i]){

                        dist[To[i]]=dist[front]+;

                        l[++tl]=To[i];

                    }

                }

        }

    return dist[r*c*+]!=-;

}

int DFS(int now,int x)

{

    if(now==r*c*+ || !x)return x;

    int res=;

        for(int i=head[now];i!=- && x;i=nxt[i]){

            if(dist[now]+==dist[To[i]]&&W[i]){

                int DK=DFS(To[i],min(x,W[i]));

                W[i]-=DK;W[i^]+=DK;

                x-=DK;res+=DK;

            }

        }

    if(!res)dist[now]=-;

    return res;

}

void Dinic()

{

    int ans=;

    while(BFS())

        ans+=DFS(,2e9);

    printf("%d",L-ans);

    return ;

}

int main()

{

//  freopen("x.txt","r",stdin);

    scanf("%d%d%d",&r,&c,&d);

    memset(nxt,-,sizeof nxt);

    memset(head,-,sizeof head);

    register int i,j,k,h;

    #define Size ( r*c )

    #define fr ( (i-1)*c+j )

    #define to ( (k-1)*c+h )

        for(i=;i<=r;i++){

            cin>>S;

                for(j=;j<S.size();j++){

                    a[i][j+]=S[j]-'';

                }

        }

        for(i=;i<=r;i++){

            cin>>S;

                for(j=;j<=S.size();j++){

                    if(S[j-]=='L'){

                        L++;//求蜥蜴总数

                        add(,fr,);

                        add(fr,,);

                    }

                }

        }

        for(i=;i<=r;i++)

            for(j=;j<=c;j++){

                if(!a[i][j])continue;

                add(fr,fr+Size,a[i][j]);

                add(fr+Size,fr,);

                for(k=;k<=r;k++)

                    for(h=;h<=c;h++){

                        if(i==k&&j==h)continue;

                        if(a[k][h]/*减少边的总量*/&&check(i,j,k,h)){

                            add(fr+Size,to,2e9);

                            add(to,fr+Size,);

                        }

                    }

            }

        for(i=;i<=r;i++)

            for(j=;j<=c;j++){

                if(i<=d || j<=d || r-i+<=d || c-j+<=d){

                    if(!a[i][j])continue;//减少边的总量

                    add(fr+Size,Size<<|,2e9);

                    add(Size<<|,fr+Size,);

                }

            }

    Dinic();

    return ;

}

巴特西

BZOJ1066_蜥蜴_KEY

最新文章

热门文章