「网络流挖坑大全」最大流最小割 错误点记录

2018年12月27日 天气：阴 心情：一般

because!——学网络流第二、三道题就WA，查错花了INF的时间

今天作为学习网络流的第二天，本人决定潜心研究记录网络流的错题

顺便补上昨天的错题

Ⅰ、炸点优化对象炸弄错了

[BJOI2006]狼抓兔子

WA Code：

int Dinic(int k,int flow)
{
    if(k==T)
        return flow;
    int i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt)
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[res]=0;//它错在这里！！！炸点炸的应该是to不是res！
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}

AC Code：

int Dinic(int k,int flow)
{
    if(k==T)
        return flow;
    int i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt)
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[to]=0;//就是这里！哼~不高兴!
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}

Ⅱ、建边没看方向 眼睛呢！

[BJOI2006]狼抓兔子

WA Code：

    for(i=1;i<=n;i++)
        for(j=1;j<m;j++)
        {
            cap=read();
            add(TtO(i,j),TtO(i,j+1),cap);//这里！
        }
    for(i=1;i<n;i++)
        for(j=1;j<=m;j++)
        {
            cap=read();
            add(TtO(i,j),TtO(i+1,j),cap);//这里！！
        }
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
        {
            cap=read();
            add(TtO(i,j),TtO(i+1,j+1),cap);//还有这里！！！
        }//别看了，我码量大~

AC Code：

    for(i=1;i<=n;i++)
        for(j=1;j<m;j++)
        {
            cap=read();
            add(TtO(i,j),TtO(i,j+1),cap);
            add(TtO(i,j+1),TtO(i,j),cap);//这样就对了
        }
    for(i=1;i<n;i++)
        for(j=1;j<=m;j++)
        {
            cap=read();
            add(TtO(i,j),TtO(i+1,j),cap);
            add(TtO(i+1,j),TtO(i,j),cap);//嗯，就是这样
        }
    for(i=1;i<n;i++)
        for(j=1;j<m;j++)
        {
            cap=read();
            add(TtO(i,j),TtO(i+1,j+1),cap);
            add(TtO(i+1,j+1),TtO(i,j),cap);//不错，这样很Nice
        }

不过这位大佬想出了省一半空间的方法瑟瑟发抖

这个事情告诉我们：珍惜时间，好好看题

Ⅲ、边的方向弄错

[CQOI2009]跳舞

WA Code：

    for(i=1;i<=(n<<1);i++)//偷懒而已……
    {
        add(i,i+(n<<1),n);
        add(i,i+(n<<2),k);
    }

AC Code：

    for(i=1;i<=n;i++)
    {
        add(i,i+(n<<1),n);
        add(i,i+(n<<2),k);
    }
    for(i=n+1;i<=(n<<1);i++)//反过来就对了！
    {
        add(i+(n<<1),i,n);
        add(i+(n<<2),i,k);
    }

这个事情告诉我们：年轻人切莫偷懒

Ⅳ、遍历边的时候写错

[CQOI2009]跳舞

WA Code：

int Dinic(int k,int flow)
{
    if(k==T)
        return flow;
    int i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].to)//厉害吧~
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[to]=0;
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}

AC Code：

int Dinic(int k,int flow)
{
    if(k==T)
        return flow;
    int i,to,cap,res,rest=flow;
    for(i=head[k];i&&rest;i=b[i].nxt)//这样才对嘛！众人：智障！
    {
        to=b[i].to;cap=b[i].cap;
        if(cap&&deep[to]==deep[k]+1)
        {
            res=Dinic(to,min(rest,cap));
            if(!res)
                deep[to]=0;
            b[i].cap-=res;
            b[i^1].cap+=res;
            rest-=res;
        }
    }
    return flow-rest;
}

13:04，这是今天第二次，查错查了半天，我才学了两天啊！

Ⅴ、汇点变量T混用

教辅的组成

WA Code：

    S=n1+n1+n2+n3+1;T=n1+n1+n2+n3+2;//T是汇点~
    for(i=1;i<=n3;i++)
        add(S,i+n1+n2,1);
    for(i=1;i<=n2;i++)
        add(i+n1,T,1);
    for(i=1;i<=n1;i++)
        add(i+n1+n2+n3,i,1);
    T=read();//T记录边数……黑脸
    while(T--)
    {
        x=read();y=read()+n1;
        add(x,y,1);
    }
    T=read();//还有这里……居然！吐血
    while(T--)
    {
        x=read()+n1+n2+n3;y=read()+n1+n2;
        add(y,x,1);
    }

AC Code：

    S=n1+n1+n2+n3+1;T=n1+n1+n2+n3+2;
    for(i=1;i<=n3;i++)
        add(S,i+n1+n2,1);
    for(i=1;i<=n2;i++)
        add(i+n1,T,1);
    for(i=1;i<=n1;i++)
        add(i+n1+n2+n3,i,1);
    m=read();//换个变量就行了……
    while(m--)
    {
        x=read();y=read()+n1;
        add(x,y,1);
    }
    m=read();//我肯定是傻了……
    while(m--)
    {
        x=read()+n1+n2+n3;y=read()+n1+n2;
        add(y,x,1);
    }

Ⅵ、边的数组范围开小

教辅的组成

WA Code：

#define M 50010//少了20000！
using namespace std;
struct node{
    int to,cap;
    int nxt;
    node(int a,int b):to(a),cap(b){    }
    node(){    }
}b[M<<1];

AC Code：

#define M 70010//看来真的要多加一个zero才行！
using namespace std;
struct node{
    int to,cap;
    int nxt;
    node(int a,int b):to(a),cap(b){    }
    node(){    }
}b[M<<1];

13:53 今天第三次 Orz网络流

Ⅶ、建边交错混杂弄反 h^ovny：@#%&？！

[USACO07OPEN]吃饭Dining

WA Code：

    for(i=1;i<=F;i++)//看出来哪里错了吗？
        add(S,n+i,1);
    for(i=1;i<=D;i++)//混杂弄反emmm
        add(n+F+i,T,1);
    for(i=1;i<=n;i++)//边弄反
        add(i,n+F+D+i,1);

AC Code：

    for(i=1;i<=D;i++)//这才是正解嘛！
        add(S,n+F+i,1);
    for(i=1;i<=F;i++)
        add(n+i,T,1);
    for(i=1;i<=n;i++)
        add(n+F+D+i,i,1);

h^ovny：脑白金？！