呜呜呜,蒟蒻求救

P3376 【模板】网络最大流

挪威的森林 @ 2019-09-23 15:29:41

代码很短,真的没找到哪错了,但是全wa了。

/*
   与ek算法有异曲同工之妙,ek太过暴力。
   dinic是将ek分层之后再搞。
   bfs用于建图,dfs用于增广(一层就一个了)。
*/
#include<bits/stdc++.h>  //存反向边,异或一下
using namespace std; const int maxn = 1e5+10;
const int inf=1e9+7;
struct node{
    int to,nx,we;
}s[maxn<<2];   int head[maxn>>2],cnt=1,dep[maxn>>2];
int n,m,st,en;
void add(int u,int v,int w){
    s[++cnt].to=v;s[cnt].nx=head[u];head[u]=cnt;s[cnt].we=w;
}
int bfs(int st,int en){
//    memset(dep,0,sizeof(dep));
    for(int i=1;i<=n;i++) dep[i]=0;
    queue<int> q;
    q.push(st);
    dep[st]=1;
    while(!q.empty()){
        int t=q.front(); q.pop();
        for(int i=head[t];i;i=s[i].nx){
            int to=s[i].to;  //边权为0了就不用建图了
            //如果再连边的话图形状不会改变,会死循环。
            if(s[i].we==0||dep[to]) continue;
            dep[to]=dep[t]+1;
            q.push(to);
        }
    }
    if(dep[en]) return 1; return 0;
}
int dfs(int u,int v,int mi){
    if(u==v||mi==0) return mi;
    int res=0;
    for(int i=head[u];i;i=s[i].nx){
        int to=s[i].to,tmp;
        //容量最小值为目前的容量或者其他
        if(dep[to]==dep[u]+1&&(tmp=dfs(to,v,min(mi,s[i].we)))){
            s[i].we-=tmp;
            s[i^1].we+=tmp;
            res+=tmp; mi-=tmp;  //当前流量减
        }
    }
    return res;
}
void dinic(){
    int res=0;
    while(bfs(st,en)){  //有增广路就分层后增广
        res+=dfs(st,en,inf);  //inf表示目前拥有的流量
    }
    cout<<res<<endl;
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>st>>en;
    for(int i=1;i<=m;i++){
        int a,b,c; cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    dinic();
    return 0;
}

by 1saunoya @ 2019-09-23 15:31:58

反向边 为 0


by 挪威的森林 @ 2019-09-25 22:17:01

@清风ღ

后来才发现(蒟蒻流泪)


|