【求助】Dinic算法 最后两个点不过

P3376 【模板】网络最大流

liuzihaohao @ 2023-12-09 09:41:39

提交记录

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct Edge{
    int w,v,nxt;
}e[10005];int head[279],tot=0;
void addedge(int u,int v,int w){
    e[tot].w=w;
    e[tot].nxt=head[u];
    e[tot].v=v;
    head[u]=tot++;
}
int m,n,s,t;
const int INF=0x3f3f3f3f;
int cur[10010],dep[10010];
bool bfs(){
    queue<int>q;
    memset(dep,0,sizeof(dep));
    dep[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int v,i=head[u];i;i=e[i].nxt){
            v=e[i].v;
            if(dep[v]==0&&e[i].w){
                dep[v]=dep[u]+1;
                if(v==t){
                    return true;
                }
                q.push(v);
            }
        }
    }
    return false;
}
int dfs(int u,int maxflow){
    if(u==t){
        return maxflow;
    }
    int sum=0;
    for(int v,i=cur[u];i;i=e[i].nxt){
        v=e[i].v;
        cur[u]=i;
        if(dep[v]==dep[u]+1&&e[i].w){
            int f=dfs(v,min(maxflow,e[i].w));
            sum+=f;
            maxflow-=f;
            e[i].w-=f;
            e[i^1].w+=f;
            if(maxflow==0){
                break;
            }
        }
    }
    if(sum==0){
        dep[u]=0;
    }
    return sum;
}
int dinic(){
    int maxflow=0;
    while(bfs()){
        for(int i=1;i<=tot;i++){
            cur[i]=head[i];
        }
        maxflow+=dfs(s,INF);
    }
    return maxflow;
}
signed main(void){
//  freopen("P3376_2.in","r",stdin);
    memset(head,0,sizeof(head));
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,0);
    }
    printf("%lld\n",dinic());
    return 0;
}

by Misty7 @ 2023-12-09 10:00:42

@liuzihaohao 你的head初始要是-1,因为您的第一条边编号就是0


by liuzihaohao @ 2023-12-09 10:25:34

@Misty_Hazers 感谢大佬,已过


|