BZOJ1066 网络流

拆点，将一个柱子拆成入点和出点，入点出点之间的容量就是柱子的容量

　　 1066: [SCOI2007]蜥蜴

在一个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

 #include<cstdio>

 #include<queue>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int INF=0x3f3f3f3f;

 int r,c,d,st,ed,tot;

 int dis[],head[];

 char mp[];

 struct node

 {

     int x,y,ab;

     bool ri;

 } p[];

 struct line

 {

     int to,next,w;

 } e[];

 void add(int u,int v,int w)

 {

     e[tot].to=v;

     e[tot].next=head[u];

     e[tot].w=w;

     head[u]=tot++;

 }

 bool bfs()

 {

     queue<int>Q;

     Q.push(st);

     memset(dis,-,sizeof(dis));

     dis[st]=;

     while(!Q.empty())

     {

         int u=Q.front();

         Q.pop();

         for(int i=head[u]; i+; i=e[i].next)

         {

             int v=e[i].to;

             if(dis[v]==-&&e[i].w>)

             {

                 dis[v]=dis[u]+;

                 if(v==ed) return true;

                 Q.push(v);

             }

         }

     }

     return false;;

 }

 int dfs(int u,int low)

 {

     if(u==ed) return low;

     int ans=low,a;

     for(int i=head[u]; i+; i=e[i].next)

     {

         int v=e[i].to;

         if(e[i].w>&&dis[v]==dis[u]+&&(a=dfs(v,min(ans,e[i].w))))

         {

             e[i].w-=a;

             e[i^].w+=a;

             ans-=a;

             if(!ans) return low;

         }

     }

     if(ans==low) dis[u]=-;

     return low-ans;

 }

 bool Ju(const node &A,const node &B)

 {

     int dis=(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);

     if(dis>d) return false;

     return true;

 }

 int dinic()

 {

     int ans=;

     while(bfs())

     {

         ans+=dfs(,INF);

     }

     return ans;

 }

 int main()

 {

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

     int cont=,ct=;

     tot=;

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

     {

         scanf("%s",mp);

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

         {

             p[++cont].x=i;

             p[cont].y=j;

             p[cont].ab=mp[j]-'';

         }

     }

     st=,ed=*cont+;

     memset(head,-,sizeof(head));

     cont=;

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

     {

         scanf("%s",mp);

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

             if(mp[j]=='L') p[++cont].ri=,++ct;

             else p[++cont].ri=;

     }

     for(int i=; i<=cont; ++i)

     {

         if(p[i].ab)

         {

             add(i,i+cont,p[i].ab), add(i+cont,i,);

             if(p[i].ri) add(,i,),add(i,,);

             for(int j=; j<=cont; ++j)

             {

                 if(i==j) continue;

                 if(p[j].ab&&Ju(p[i],p[j]))

                 {

                     add(i+cont,j,INF);

                     add(j,i+cont,);

                 }

             }

             if(p[i].x-d<||p[i].x+d>=r||p[i].y-d<||p[i].y+d>=c)

             {

                     add(i+cont,ed,INF);

                     add(ed,i+cont,);

             }

         }

     }

     int ans=dinic();

     printf("%d\n",ct-ans);

 }

巴特西

BZOJ1066 网络流

Input

Output

Sample Input

Sample Output

最新文章

热门文章