萌新刚学网络流,Dinic求助

P3376 【模板】网络最大流

SuperCowHorse @ 2022-12-29 19:32:04

RT。

37pts。

#include<bits/stdc++.h>
#define ll long long
#define do double
using namespace std;
const ll inf=0x3f3f3f3f;
const int maxn=205,maxm=5005;
int n,m,s,t;
struct edge{
    int v;ll w;int next;
}e[maxm<<1];int head[maxn],cnt;
inline void add(int u,int v,ll w){
    e[++cnt]=edge{v,w,head[u]};
    head[u]=cnt;
}
inline void ADD(int u,int v,ll w){add(u,v,w);add(v,u,w);}
int dis[maxn],now[maxn];
inline bool bfs(int s,int t){
    memset(dis,0,sizeof(dis));
    queue<int>q;
    dis[s]=1;q.push(s);
    now[s]=head[s];
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next){
            int v=e[i].v;
            if(!dis[v]&&e[i].w>0){
                dis[v]=dis[u]+1;
                now[v]=head[v];
                q.push(v);
                if(v==t) return 1;
            }
        }
    }
    return 0;
}
inline ll dfs(int u,int t,ll x){
    if(u==t) return x;
    ll y=x;
    for(int i=now[u];i&&y;i=e[i].next){
        now[u]=i;
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].w>0){
            ll k=dfs(v,t,min(y,e[i].w));
            if(k==0) dis[v]=0;
            e[i].w-=k;
            e[i^1].w+=k;
            y-=k;
        }
    }
    return x-y;
}
inline ll Dinic(int s,int t){
    ll ans=0;
    while(bfs(s,t))
        ans+=dfs(s,t,inf);
    return ans;
}
signed main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1,u,v;i<=m;++i){
        ll w;
        scanf("%d%d%lld",&u,&v,&w);
        add(u,v,w);add(v,u,0);
    }
    printf("%lld",Dinic(s,t));
    return 0;
}

by liangbowen @ 2022-12-29 19:48:13

@chenye3 链式前向星定义变量时 cnt=1


by liangbowen @ 2022-12-29 19:49:35

实测通过。因为如果你需要使用异或的性质,为了使得i^1是反向边,第一条边的下标就必须从偶数开始,即cnt=1。


by SuperCowHorse @ 2022-12-29 19:50:54

@liangbowen 谢谢大佬qwq


|