数据太淼
查看原帖
数据太淼
340716
luckyzjy楼主2025/7/2 17:35
#include <bits/stdc++.h>
using namespace std;
const int N=2e4+5,inf=2e9;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define int long long
namespace flow
{
    int head[N],cur[N],ver[N],nxt[N],edge[N],tot=1,gap[N],dep[N];
    void add(int x,int y,int z)
    {
        ver[++tot]=y;
        nxt[tot]=head[x];
        edge[tot]=z;
        head[x]=tot;
    }
    void adde(int x,int y,int z)
    {
        add(x,y,z);
        add(y,x,0);
    }
    int n,m,s,t,maxflow;
    int dfs(int x,int flow)
    {
        //cout<<x<<" "<<flow<<endl;
        if(x==t) return flow;
        int used=0;
        for(int &i=cur[x];i;i=nxt[i])
        {
            int y=ver[i];
            //cout<<x<<"  "<<y<<endl;
            if(edge[i]&&dep[y]==dep[x]-1)
            {
                int rlow=dfs(y,min(edge[i],flow-used));
                edge[i]-=rlow;edge[i^1]+=flow;used+=rlow;
                if(used==flow) return used;
            }
        }
        cur[x]=head[x];
        if(!--gap[dep[x]]) dep[s]=n+2;
        gap[++dep[x]]++;
        return used;
    }
    void doisap()
    {
        
        memset(gap,0,sizeof gap);
        memset(dep,0,sizeof dep);
        gap[0]=n;
        for(int i=1;i<=n;i++) cur[i]=head[i];
        while(dep[s]<=n) {maxflow+=dfs(s,inf);}
        return;
    }
}using namespace flow;



signed main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;cin>>x>>y>>z;
        adde(x,y,z);
    }
    doisap();cout<<maxflow<<endl;
    //cerr<<"ok\n";
    return 0;
}

这份代码实现的最大流算法有误
具体地 dfs函数中的

edge[i^1]+=flow;

应当为

edge[i^1]+=rlow;

这个错误很zz 但是这份代码通过了本题 事实上 它在某OJ的模板题上只能获得分 令人唏嘘
所以数据太淼

2025/7/2 17:35
加载中...