如果您wa且仅wa了#10

P3376 【模板】网络最大流

wxk123 @ 2023-08-17 17:14:51

以我的代码为例子,请检查dfs函数中f=dfs处的参数是否打错了

#include<iostream>
#include<string.h>
#include<queue> 
using namespace std;
int N,M,S,T;
#define int long long
const int MAXN=1000500;
struct B{
    int u,v,w,next;
}p[5000005];
int head[1000500],cur[1000500],id=2;
int flag[205][205];
void build(int u,int v,int w){
    p[id].u=u;
    p[id].v=v;
    p[id].w=w;
    p[id].next=head[u];
    head[u]=id;
    id++;
}
int deep[MAXN];
bool bfs(int u,int t){queue<int>que;
    memset(deep,-1,sizeof(deep));
    for(int i=1;i<=N;i++)
    cur[i]=head[i];
    deep[u]=0;
    que.push(u);
    while(!que.empty()){
        int uu=que.front();
        que.pop();
         for(int i=head[uu];i+1;i=p[i].next){
            int v=p[i].v;
            if(deep[v]==-1&&p[i].w>0){
                deep[v]=deep[uu]+1;
                que.push(v); 
                if(v==t)
                return true;
            } 
         } 
    } 
    if(deep[t]!=-1)
    return true;
    return false;
} 
int dfs(int u,int minn){
    int left=minn;
    if(u==T||minn==0)
    return minn;
    int f=0;
    for(int i=cur[u];i+1;i=p[i].next){
        int v=p[i].v;
        if(deep[u]+1==deep[v]&&p[i].w>0&&( f=dfs(v,min(left,p[i].w)))){ //我之前这里写的是dfs(v,min(minn,p[i].w)).....
            left-=f;
            p[i].w-=f;
            p[i^1].w+=f;
        }           
        if(!left)
            break; 
            cur[u]=i;//注意当前弧优化的位置
    }
    return minn-left;
}
int dinic(int u,int v){
    int ans=0;
    while(bfs(u,v)){
        ans+=dfs(u,0x3f3f3f3f3f3f3f3f);
    }
    return ans;
}
signed main(){
    //freopen("1.in","r",stdin);
    memset(head,-1,sizeof(head));
    memset(cur,-1,sizeof(cur));
    cin>>N>>M>>S>>T;
    for(int i=1;i<=M;i++){
        int u,v,w;
        cin>>u>>v>>w;
//      if(!flag[u][v]){
//              flag[u][v]=id;flag[v][u]=id+1;
                build(u,v,w);
                build(v,u,0);
//      }
//      else{
//          p[flag[u][v]].w+=w;
//      }

    }

    cout<<dinic(S,T);

}

by Edgebright @ 2023-08-18 17:49:20

%%%谢谢大佬,刚好错了这个点


by renqitian @ 2023-12-07 01:48:38

太谢谢了,大佬orz


|