求助

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-03-02 12:34:36

什么等价?


by 为依相逢 @ 2019-03-02 19:08:40

@lyh0313 语句好像等价吧。。。


上一页 |