求助

P3376 【模板】网络最大流

为依相逢 @ 2019-01-31 21:34:27

Dinic算法,初打,好像问题是死循环,请问哪里错了?

格式不对不要吐槽我,我尽力了,大括号都改成不换行的了

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int Maxn=20000;
const int Maxm=1000000;

struct Edge{
    int next,en,maxl;
}a[Maxm*2+9];

int q[Maxn+9];

int b[Maxn+9],c[Maxn+9],s,t,max_sum_l,n,m,x,y,tmp;
bool j[Maxn+9];

int t1(int num){
    return (num<<1)-1;
}

int t2(int num){
    return (num<<1)-2;
}

void jr(int num,int bn,int en,int maxl){
    int tmp1=t1(num);
    int tmp2=t2(num);

    a[tmp1].en=en;
    a[tmp1].next=b[bn];
    a[tmp1].maxl=maxl;
    b[bn]=tmp1;

    a[tmp2].en=bn;
    a[tmp2].next=b[en];
    a[tmp2].maxl=0;
    b[en]=tmp2;
    return;
}

int bfs(){
    memset(c,0,sizeof(c));
    memset(q,0,sizeof(q));
    memset(j,false,sizeof(j));
    int l=1;
    int r=1;
    q[r]=s;
    c[q[r]]=1;
    j[s]=true;
    while (l<=r){
        for (int i=b[q[l]];i!=0;i=a[i].next)
        if (!j[a[i].en] && a[i].maxl!=0){
            q[++r]=a[i].en;
            c[q[r]]=c[q[l]]+1;
            j[a[i].en]=true;
        }
        l++;
    }
    return c[t];
}

int dfs(int nownum,int now_max_l){
    if (now_max_l==0) return 0;
    int ans=0,res;
    for (int i=b[nownum];i!=0;i=a[i].next)
    if (c[a[i].en]==c[nownum]+1)
        if (res=dfs(a[i].en,min(a[i].maxl,now_max_l))>0){
            a[i].maxl-=res;
            a[i^1].maxl+=res;
            ans+=res;
        }
    return ans;
}

int dinic_work(){
    int ans=0;
    while (bfs())
        ans+=dfs(s,1<<30);
    return ans;
}

int main(){
    memset(b,-1,sizeof(b));
    scanf("%d%d%d%d",&n,&m,&s,&t);
    max_sum_l=1<<30;
    for (int i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&tmp);
        jr(i,x,y,tmp);
    }
    cout<<min(dinic_work(),max_sum_l);

    return 0;
}

by lyh0313 @ 2019-01-31 21:46:03

@zlym: 你的边集数组b初值为-1,但两次调用都是i!=0,应该为i!=-1

没崩溃是因为下标没有溢出太多


by lyh0313 @ 2019-01-31 21:47:17

@ zlym


by 为依相逢 @ 2019-01-31 21:53:33

@lyh0313 ok谢谢

我就知道是沙雕错误


by 为依相逢 @ 2019-01-31 21:54:43

@lyh0313 等下,还是死循环


by lyh0313 @ 2019-01-31 22:08:36

dinic算法中,dfs到达汇点要直接返回当前流!!

  if (now_max_l==0) return 0;

这句后面加上

    if(nownum==t) return now_max_l;

就可以了


by 为依相逢 @ 2019-01-31 22:13:18

@lyh0313 emmm...5WA3TLE


by 为依相逢 @ 2019-01-31 22:13:40

我觉得剩下的还是沙雕错误。。。


by lyh0313 @ 2019-01-31 22:45:11

你把dfs函数改成

int dfs(int nownum,int now_max_l){
    if(nownum==t) return now_max_l;
    int ans=0,res;
    for (int i=b[nownum];i!=0;i=a[i].next)
    if (c[a[i].en]==c[nownum]+1&&a[i].maxl>0)
        {
            res=dfs(a[i].en,min(a[i].maxl,now_max_l));
            a[i].maxl-=res;
            a[i^1].maxl+=res;
            ans+=res;
            now_max_l-=res;
            if(now_max_l==0) return ans;
        }
    return ans;
}

具体上网搜dinic算法吧!

这是算法问题,模板打错了!!

并非沙雕错误!


by 为依相逢 @ 2019-02-01 08:27:30

@lyh0313 emmm好吧。。。


by 为依相逢 @ 2019-03-02 10:38:47

@lyh0313 我看怎么是等价的。。。


| 下一页