bzoj1001/洛谷 P4001 [BJOI2006]狼抓兔子 题解【网络流】【最小割】

作者: wjyyy 分类: 最小割,网络流,解题报告 发布时间: 2018-09-03 11:47

点击量:6

 

    弃isap从dinic之路……

 

题目描述

现在小朋友们最喜欢的”喜羊羊与灰太狼”,话说灰太狼抓羊不到,但抓兔子还是比较在行的,而且现在的兔子还比较笨,它们只有两个窝,现在你做为狼王,面对下面这样一个网格的地形:

左上角点为(1,1),右下角点为(N,M)(上图中N=3,M=4).有以下三种类型的道路

1:(x,y)<==>(x+1,y)

2:(x,y)<==>(x,y+1)

3:(x,y)<==>(x+1,y+1)

道路上的权值表示这条路上最多能够通过的兔子数,道路是无向的. 左上角和右下角为兔子的两个窝,开始时所有的兔子都聚集在左上角(1,1)的窝里,现在它们要跑到右下角(N,M)的窝中去,狼王开始伏击这些兔子.当然为了保险起见,如果一条道路上最多通过的兔子数为K,狼王需要安排同样数量的K只狼,才能完全封锁这条道路,你需要帮助狼王安排一个伏击方案,使得在将兔子一网打尽的前提下,参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。

输入输出格式

输入格式:

第一行为N,M.表示网格的大小,N,M均小于等于1000。

接下来分三部分

第一部分共N行,每行M-1个数,表示横向道路的权值。

第二部分共N-1行,每行M个数,表示纵向道路的权值。

第三部分共N-1行,每行M-1个数,表示斜向道路的权值。

输出格式:

输出一个整数,表示参与伏击的狼的最小数量。

输入输出样例

输入样例#1:

3 4
5 6 4
4 3 1
7 5 3
5 6 7 8
8 7 6 5
5 5 5
6 6 6
输出样例#1:

14

题解:

    isap太难调了……过不了样例以为是isap问题,结果改写dinic发现还是过不了?但是写了写dinic发现dinic好写太多了常数还小qaq。

 

    这个题题意要求就是最小割,但是这个题是可以反向跑的,也就是说路是双向的。我们是否需要建立双向的流边呢?

 

    我们知道,增广一条道路时,会把它的反向边增加上正向边减小的值。这样也相当于成环,而我们如果独立地建立双向流边,达成的效果是一样的,因此可以在一开始加边的时候,就把反向流量设为同样的大小,这样既满足题意,又符合我们的思维,也方便了增广路的运作。(如果建立两组边的话,处理不好会MLE)

 

吐槽isap:

    isap要开的数组太多了。。。还有三四个细节每次写都会出错……就当学会了一种思维吧。还是dinic大法好(逃

 

Code:

#include<cstdio>
#include<cstring>
struct edge
{
    int n,v;
    int nxt;
    edge(int n,int nxt,int v)
    {
        this->n=n;
        this->nxt=nxt;
        this->v=v;
    }
    edge(){}
}e[6000000];
int head[1010000],ecnt=-1;
void add(int from,int to,int v)
{
    e[++ecnt]=edge(to,head[from],v);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to],v);//反向流量也设成v
    head[to]=ecnt;
}
int n,m;
int pla(int x,int y)
{
    return (x-1)*m+y;
}
int sum=0;
int q[1111111],l=0,r=0;
int d[1000001],cur[1000001];
bool bfs()//bfs过程
{
    memset(d,0,sizeof(d));
    d[1]=1;
    l=0,r=0;
    q[++r]=1;
    while(l<r)
    {
        int x=q[++l];
        cur[x]=head[x];
        for(int i=head[x];~i;i=e[i].nxt)
            if(e[i].v&&!d[e[i].n])
            {
                d[e[i].n]=d[x]+1;
                q[++r]=e[i].n;
            }
    }
    return d[n*m]>0;
}
int dinic(int x,int mx)
{
    if(x==n*m)//到达终点
        return mx;
    int rst=mx;
    for(int i=cur[x];(~i)&&rst;i=e[i].nxt)
        if(e[i].v&&d[e[i].n]==d[x]+1)
        {
            int t=dinic(e[i].n,rst<e[i].v?rst:e[i].v);
            if(!t)
                d[e[i].n]=0;
            e[i].v-=t;//增广
            e[i^1].v+=t;
            rst-=t;
        }
    return mx-rst;
}
int main()
{
    memset(head,-1,sizeof(head));
    int u,v,w;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        for(int j=1;j<m;++j)
        {
            scanf("%d",&w);
            add(pla(i,j),pla(i,j+1),w);
        }
    for(int i=1;i<n;++i)
        for(int j=1;j<=m;++j)
        {
            scanf("%d",&w);
            add(pla(i,j),pla(i+1,j),w);
        }
    for(int i=1;i<n;++i)
        for(int j=1;j<m;++j)
        {
            scanf("%d",&w);
            add(pla(i,j),pla(i+1,j+1),w);
        }
    int sum=0;
    while(bfs())
    {
        int t=dinic(1,0x3fffffff);
        while(t)
        {
            sum+=t;
            t=dinic(1,0x3fffffff);
        }
    }
    printf("%d\n",sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */