假的Dinic

P3376 【模板】网络最大流

7KByte @ 2020-06-17 16:53:01

Rt,估计以前写的都是错的,但是为啥从没有出现过问题。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 205
#define M 5005
typedef long long ll; 
using namespace std;
int h[N],tot=1;
struct edge{
    int to,nxt,cap;
}e[M<<1];
void add(int x,int y,int z){
    e[++tot].nxt=h[x];h[x]=tot;e[tot].cap=z;e[tot].to=y;
}
int n,m,s,t,d[N],cur[N];
queue<int>q;
bool bfs(){
    memset(d,0,sizeof(d));
    d[s]=1;q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        cur[x]=h[x];
        for(int i=h[x];i;i=e[i].nxt)
            if(e[i].cap&&!d[e[i].to])
                d[e[i].to]=d[x]+1,q.push(e[i].to);
    }
    return d[t];
}
int dfs(int x,int flow){
    if(x==t)return flow;
    int res=flow;
    for(int &i=cur[x];i;i=e[i].nxt){
        if(!res)return flow;
        if(e[i].cap&&d[x]+1==d[e[i].to]){
            int now=dfs(e[i].to,min(res,e[i].cap));
            if(!now)d[e[i].to]=1;
            else{
                e[i].cap-=now;
                e[i^1].cap+=now;
                res-=now;
            }
        }
    }
    return flow-res;
}
int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    rep(i,1,m){
        int x,y,z;scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);add(y,x,0);
    }
    ll ans=0;
    while(bfs())ans+=dfs(s,0x7fffffff);
    printf("%lld\n",ans);
    return 0;
}

by smarthehe @ 2020-06-17 17:43:43

@几何之舞丶 Undefined Behavior


by smarthehe @ 2020-06-17 17:46:03

@Inf_Voltage

这个的区别是,如果你在循环一开始写,可能这条边没有流满你却进了下一条边,把下一条边当成了当前弧。前一条边还没有流满就废了。


by WrongAnwser @ 2020-06-19 09:11:29

@smarthehe

感谢大佬,如果没看到您的回复我估计这辈子写的都是假的Dinic了(原来loj模板题时间跑30ms才是正常的我原来都跑的是500ms以上)


上一页 |