王茗仟 @ 2022-11-04 20:28:48

#define int long long 
#define re  register
#define in inline
#define max(a,b) ((a)>(b)?a:b)
#define min(a,b) ((a)<(b)?a:b)
using namespace std;
const int MAXN=1e4+10;
const int MAXM=2e5+19;
const int INF=0x3f3f3f3f3f;

in int read(){
    re int x=0,f=0;re char c=getchar();
    while(!isdigit(c)) f|=(c=='-'),c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f?-x:x;
}

int n,m,s,t,dis[MAXN],cur[MAXN];

struct edge{
    int u,v,w;
    int nx;
}e[MAXM];
int head[MAXN],tot;

in void  add(int u,int v,int w){
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nx=head[u];
    head[u]=tot++;
}

bool bfs(){
//广搜一下测一下剩下点的深度，顺便找出增广路
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(s);
    dis[s]=0;
    cur[s]=head[s];//cur是当前弧优化的宝贝
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].nx){
            int v=e[i].v;
            if(dis[v]==-1&&e[i].w){
                dis[v]=dis[u]+1;
                cur[v]=head[v];
                if(v==t){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;//不存在增广路了，可以结束le
}

int dfs(int u,int lim){
// 当前节点     能增加的最大流量
//深搜？？也就是增广一下，给下流
    if(u==t){
        return lim;
    }

    int flow=0;//从u点分出去的
    for(int i=cur[u];~i;i=e[i].nx){
        cur[i]=i;//当前弧优化，很新对你来说，（走过就不再走了）
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].w){
            int minf=dfs(v,min(e[i].w,lim-flow));//求要给v多少
//limit-flow给这条边能分的最多有多少
            e[i].w-=minf;
            e[i^1].w+=minf;
            flow+=minf;
            if(flow==lim){
            //全分完了直接结束吧
                return flow;
            }
        }   
    }
    return flow;

}

int dinic(){
    int ans=0;
    while(bfs()){
    //  cout<<ans<<endl;
        ans+=dfs(s,INF);
    }
    return ans;
}

signed main(){
    n=read();m=read();s=read();t=read();
    memset(head,-1,sizeof(head));
    for(re int i=1;i<=m;i++){
        int u,v,w;
        u=read();v=read();w=read();
        add(u,v,w);add(v,u,0);
    }
    cout<<dinic()<<endl;
    return 0;
}

by IceYukino @ 2022-11-04 20:49:51

@王茗仟 不对，谁和你说当前弧优化是这么写的。。

by IceYukino @ 2022-11-04 20:50:22

当前弧是cur[u]=i，不是cur[i]=i，并且cur在bfs里面的赋值是在if外面

by treeqwq @ 2022-11-04 20:50:41

草，cur[i]=i是个啥

by 王茗仟 @ 2022-11-04 20:51:18

@gqh_juruo .

我认为并不是，在里面是因为能走那个点才给他设置cur的，不能走没必要设置

我改成这样还是错的，和您的意思相符吗

bool bfs(){
//广搜一下测一下剩下点的深度，顺便找出增广路
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(s);
    dis[s]=0;
    cur[s]=head[s];//cur是当前弧优化的宝贝
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=head[u];~i;i=e[i].nx){
            int v=e[i].v;
            cur[v]=head[v];
            if(dis[v]==-1&&e[i].w){
                dis[v]=dis[u]+1;
                if(v==t){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;//不存在增广路了，可以结束le
}

by IceYukino @ 2022-11-04 20:51:33

@王茗仟

#include<bits/stdc++.h>
#define int long long 
#define re  register
#define in inline
#define max(a,b) ((a)>(b)?a:b)
#define min(a,b) ((a)<(b)?a:b)
using namespace std;
const int MAXN=1e4+10;
const int MAXM=2e5+19;
const int INF=0x3f3f3f3f3f;

in int read(){
    re int x=0,f=0;re char c=getchar();
    while(!isdigit(c)) f|=(c=='-'),c=getchar();
    while(isdigit(c)) x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return f?-x:x;
}

int n,m,s,t,dis[MAXN],cur[MAXN];

struct edge{
    int u,v,w;
    int nx;
}e[MAXM];
int head[MAXN],tot;

in void  add(int u,int v,int w){
    e[tot].u=u;
    e[tot].v=v;
    e[tot].w=w;
    e[tot].nx=head[u];
    head[u]=tot++;
}

bool bfs(){
//广搜一下测一下剩下点的深度，顺便找出增广路
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(s);
    dis[s]=0;
    cur[s]=head[s];//cur是当前弧优化的宝贝
    while(q.size()){
        int u=q.front();
        q.pop();
        cur[u]=head[u];
        for(int i=head[u];~i;i=e[i].nx){
            int v=e[i].v;
            if(dis[v]==-1&&e[i].w){
                dis[v]=dis[u]+1;
                if(v==t){
                    return 1;
                }
                q.push(v);
            }
        }
    }
    return 0;//不存在增广路了，可以结束le
}

int dfs(int u,int lim){
// 当前节点     能增加的最大流量
//深搜？？也就是增广一下，给下流
    if(u==t||!lim){
        return lim;
    }

    int flow=0;//从u点分出去的
    for(int i=cur[u];~i;i=e[i].nx){
        cur[u]=i;//当前弧优化，很新对你来说，（走过就不再走了）
        int v=e[i].v;
        if(dis[v]==dis[u]+1&&e[i].w){
            int minf=dfs(v,min(e[i].w,lim-flow));//求要给v多少
//limit-flow给这条边能分的最多有多少
            e[i].w-=minf;
            e[i^1].w+=minf;
            flow+=minf;
            if(flow==lim){
            //全分完了直接结束吧
                return flow;
            }
        }   
    }
    return flow;

}

int dinic(){
    int ans=0;
    while(bfs()){
    //  cout<<ans<<endl;
        ans+=dfs(s,INF);
    }
    return ans;
}

signed main(){
    n=read();m=read();s=read();t=read();
    memset(head,-1,sizeof(head));
    for(re int i=1;i<=m;i++){
        int u,v,w;
        u=read();v=read();w=read();
        add(u,v,w);add(v,u,0);
    }
    cout<<dinic()<<endl;
    return 0;
}

过了

by 王茗仟 @ 2022-11-04 20:51:42

@LSOT

我错了，我错了，我错了，我错了，我错了

by 野生林登万 @ 2022-11-04 20:51:54

草，破案了，的确是cur的锅
cur[u] = i,在dfs中

by 王茗仟 @ 2022-11-04 20:53:55

@gqh_juruo

感谢感谢，您率先点出来

cur[u]的错误

但是bfs里，我认为我是对的

by IceYukino @ 2022-11-04 20:56:12

@王茗仟 有道理，我当时没注意看，但是你看我俩写的不是一样的吗。。我是入队改，你是在if里改，一样的。

by IceYukino @ 2022-11-04 20:56:34

你写的确实是对的