「BZOJ1412」[ZJOI2009] 狼和羊的故事

2014年3月16日6,7090

Description

“狼爱上羊啊爱的疯狂，谁让他们真爱了一场；狼爱上羊啊并不荒唐，他们说有爱就有方向．．．．．．” Orez听到这首歌，心想：狼和羊如此和谐，为什么不尝试羊狼合养呢？说干就干！ Orez的羊狼圈可以看作一个n*m个矩阵格子，这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼，它们总是对羊垂涎三尺，那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆，还是要将羊狼分开来养。通过仔细观察，Orez发现狼和羊都有属于自己领地，若狼和羊们不能呆在自己的领地，那它们就会变得非常暴躁，不利于他们的成长。 Orez想要添加篱笆的尽可能的短。当然这个篱笆首先得保证不能改变狼羊的所属领地，再就是篱笆必须修筑完整，也就是说必须修建在单位格子的边界上并且不能只修建一部分。

Input

文件的第一行包含两个整数n和m。接下来n行每行m个整数，1表示该格子属于狼的领地，2表示属于羊的领地，0表示该格子不是任何一只动物的领地。

Output

文件中仅包含一个整数ans，代表篱笆的最短长度。

Sample Input

2 2
2 2
1 1

Sample Output

数据范围
10%的数据 n，m≤3
30%的数据 n，m≤20
100%的数据 n，m≤100

题解

挖掘栅栏的本质：只能建在相邻两个，且建好后使得狼和羊之间不存在通路。而割的定义是：使S集和T集不存在通路。而题目又要求建的栅栏最少，于是就是最小割问题了。

从源点向所有狼连一条∞的边，从所有羊向汇点连一条∞的边，这样就能保证狼和羊都在不同的点集里。然后再从狼到相邻的羊和空地，空地到相邻的空地和羊连一条流量为1的边，最大流求最小割即可。

或者将所有点向四周连边。。就是时间长了点

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define T 10001
using namespace std;
int head[10005],q[10005],h[10005];
int cnt=1,ans,n,m;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},mp[105][105];
struct data{int to,next,v;}e[500001];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs()
{
     int t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     q[0]=0;h[0]=0;
     while(t<w)
     {
               now=q[t];t++;i=head[now];
               while(i)
               {
                       if(e[i].v&&h[e[i].to]==-1)
                       {
                                                 h[e[i].to]=h[now]+1;
                                                 q[w++]=e[i].to;
                                                 }
                       i=e[i].next;
                       }
               }
    return h[T]==-1? 0:1;
 }
int dfs(int x,int f)
{
    if(x==T)return f;
    int w,used=0,i;
    i=head[x];
    while(i)
    {
            if(e[i].v&&h[e[i].to]==h[x]+1)
            {
                                          w=f-used;
                                          w=dfs(e[i].to,min(w,e[i].v));
                                          e[i].v-=w;
                                          e[i^1].v+=w;
                                          used+=w;
                                          if(used==f)return f;
                                          }
            i=e[i].next;
            }
    if(!used)h[x]=-1;
    return used;
}
void dinic(){while(bfs())ans+=dfs(0,inf);}
void ini()
{
     scanf("%d%d",&n,&m);
     for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
             scanf("%d",&mp[i][j]);
     }
void build()
{
     for(int i=1;i<=n;i++)
         for(int j=1;j<=m;j++)
         {
             if(mp[i][j]==1)insert(0,(i-1)*m+j,inf);
             else if(mp[i][j]==2)insert((i-1)*m+j,T,inf);
             for(int k=0;k<4;k++)
             {
                     int nowx=i+xx[k],nowy=j+yy[k];
                     if(nowx<1||nowx>n||nowy<1||nowy>m||mp[i][j]==2)continue;
                     if(mp[i][j]!=1||mp[nowx][nowy]!=1)
                     insert((i-1)*m+j,(nowx-1)*m+nowy,1);
                     }
             }
     }
int main()
{
    ini();
    build();
    dinic();
    printf("%d",ans);
    return 0;
    }

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x7fffffff

#define T 10001

using namespace std;

int head[10005],q[10005],h[10005];

int cnt=1,ans,n,m;

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0},mp[105][105];

struct data{int to,next,v;}e[500001];

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

{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}

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

{ins(u,v,w);ins(v,u,0);}

bool bfs()

{

int t=0,w=1,i,now;

memset(h,-1,sizeof(h));

q[0]=0;h[0]=0;

while(t<w)

{

now=q[t];t++;i=head[now];

while(i)

{

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[w++]=e[i].to;

}

i=e[i].next;

}

return h[T]==-1? 0:1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0,i;

i=head[x];

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic(){while(bfs())ans+=dfs(0,inf);}

void ini()

{

scanf("%d%d",&n,&m);

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

scanf("%d",&mp[i][j]);

}

void build()

{

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++)

{

if(mp[i][j]==1)insert(0,(i-1)*m+j,inf);

else if(mp[i][j]==2)insert((i-1)*m+j,T,inf);

for(int k=0;k<4;k++)

{

int nowx=i+xx[k],nowy=j+yy[k];

if(nowx<1||nowx>n||nowy<1||nowy>m||mp[i][j]==2)continue;

if(mp[i][j]!=1||mp[nowx][nowy]!=1)

insert((i-1)*m+j,(nowx-1)*m+nowy,1);

}

int main()

{

ini();

build();

dinic();

printf("%d",ans);

return 0;

}

« 「网络流24题」最小路径覆盖问题「BZOJ1934」[SHOI2007] Vote 善意的投票 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1412」[ZJOI2009] 狼和羊的故事

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论