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

点击量：226

    弃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;
}