连网络流都不会了/kk

P3376 【模板】网络最大流

Belarus @ 2020-06-19 10:13:50

如题,好久没复习了,凭印象打出来 30 分,和之前的比对了一下好像没有太大的问题,也不知道哪里错了?

#include<bits/stdc++.h>
using namespace std;
const int size=500010;
int n,m,s,t,maxflow=0;
int ver[size],head[size],edge[size],nxt[size],tot=1;
int d[size];
inline void add(int x,int y,int z){
    ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;
    ver[++tot]=z;edge[tot]=0;nxt[tot]=head[y];head[y]=tot;
}
inline bool bfs(){
    memset(d,0,sizeof(d));
    queue<int> q;
    while(!q.empty()) q.pop();
    d[s]=1;q.push(s);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=head[x];i;i=nxt[i]){
            int y=ver[i],z=edge[i];
            if(z&&(!d[y])){
                d[y]=d[x]+1;
                q.push(y);
                if(y==t) return 1;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow){
    if(x==t) return flow;
    int used=0,f;
    for(int i=head[x];i;i=nxt[i]){
        int y=ver[i],z=edge[i];
        if(z&&d[y]==d[x]+1&&used<flow){
            used+=dinic(y,min(flow-used,z));
            edge[i]-=used;
            edge[i^1]+=used;
        }
    }
    if(!used) d[x]=0;
    return used;
}
int main(){
    //freopen("P3376_4.in.txt","r",stdin);
    ios::sync_with_stdio(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;++i){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
    }
    int tmp;
    while(bfs()) 
     while(tmp=dinic(s,0x3f3f3f3f)) 
      maxflow+=tmp;
    cout<<maxflow;
    return 0;
}

by 鏡音リン @ 2020-06-19 10:17:45

这找增广路这部分写的啥啊 反正我看不懂


by Belarus @ 2020-06-19 10:24:38

@鏡音リン 我谔谔,我去比对了一下《算法进阶》上的,你可以把 rest 看成 flow-used


by pocafup @ 2020-06-19 10:39:39

inline void add(int x,int y,int z){
    ver[++tot]=y;edge[tot]=z;nxt[tot]=head[x];head[x]=tot;
    ver[++tot]=z;edge[tot]=0;nxt[tot]=head[y];head[y]=tot;
}

萌新求问,为啥第二个 ver[++tot] 等于 z


by Belarus @ 2020-06-19 10:41:42

@pocafup 草草草草草,手残了,但是为什么这都可以3AC


by pocafup @ 2020-06-19 10:43:51

@Belarus 好像还有其他锅?不过看着确实挺对的


by Belarus @ 2020-06-19 10:45:16

@pocafup 是的,还是3AC


by pocafup @ 2020-06-19 10:50:34

@Belarus 已经调出来了

问题在这里

if(z&&d[y]==d[x]+1&&used<flow){
    used+=dinic(y,min(flow-used,z));
    edge[i]-=used;
    edge[i^1]+=used;
}

您想想为啥吧


by AThousandSuns @ 2020-06-19 10:53:00

当前弧?


by Belarus @ 2020-06-19 10:58:14

@pocafup 蛤?


by _Sein @ 2020-06-19 10:59:37

@Belarus

应该是当前这条边流过去多少流量

而不是这个点已经流过去多少流量


| 下一页