MnZn求助最大流MLE

P3376 【模板】网络最大流

Benzenesir @ 2023-05-04 14:37:54

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#define ll long long
#define fp(a,b,c) for(ll a=b;a<=c;a++)
#include <tuple>
#define fd(a,b,c) for(ll a=b;a>=c;a--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr first
#define sd second
#define mod 1000000007
#define inf 0x3f3f3f3f

//#define int long long

using namespace std;

const int maxN=100+10;
struct node{int to,flow,nex;};
    struct liu{
        int idx=1;
        int head[maxN*4],cur[maxN*4],dep[maxN*4],in[maxN*4],s,t,n,m;//起点,终点,点数,边数
        node g[maxN*100];
        int vis[maxN];
        inline void add(int u,int v,int flow){
            g[++idx]={v,flow,head[u]};
            head[u]=idx;
            g[++idx]={u,0,head[v]};
            head[v]=idx;
        }
        bool bfs(){
            queue<int>q;
            memset(in,0,sizeof(in));
            memset(dep,0x3f,sizeof(dep));
            q.push(s);
            dep[s]=1;
            in[s]=1;
            while(!q.empty()){
                int temp=q.front();
                q.pop();
                for(int i=head[temp];i;i=g[i].nex)
                    if(!g[i].flow) continue;
                else if(dep[g[i].to]>dep[temp]+1){
                    dep[g[i].to]=dep[temp]+1;
                    if(!in[g[i].to])
                        in[g[i].to]=1,q.push(g[i].to);
                }
            }
            return dep[t]!=0x3f3f3f3f;
        }
        inline int dfs(int now,int cap){
            if(now==t)return cap;
            int p=cap;
            for(int &i=cur[now];i;i=g[i].nex){
                if(!p) break;
                if(!g[i].flow&&dep[g[i].to]!=dep[now]+1) continue;
                int tp=dfs(g[i].to,min(p,g[i].flow));
                if(tp) g[i].flow-=tp,g[i^1].flow+=tp,p-=tp;
                else dep[g[i].to]=-1;
            }
            return cap-p;
        }
        inline int dinic(){
            int np=0,mf=0;
            while(bfs()){
                fp(i,1,n) cur[i]=head[i];
                while(np=dfs(s,inf)) mf+=np;
            }return mf;
        }
        inline void clear(){
            memset(in,0,sizeof(in));
            memset(dep,0,sizeof(dep));
            memset(cur,0,sizeof(cur));
            memset(head,0,sizeof(head));
            idx=1;
            s=0,t=0,n=0,m=0;
        }
    }mf;//求最大独立集

signed main(){
    cin >> mf.n >> mf.m >> mf.s >> mf.t;
    int u,v,w;
    for(int i=1;i<=mf.m;++i){
        cin >> u >> v >> w;
        mf.add(u,v,w);
    }
//  for(int i=1;i<=n;++i)
//      add(i,i+n,1);
//  for(int i=1;i<=m;++i){
//      cin >> u >> v;
//      add(u+n,v,inf),add(v+n,u,inf);
//  }   
//  s+=n;
    //cout << mf.idx << endl;
    cout <<mf.dinic() << endl;;

    return 0;
} 

结构体里的代码是之前的板子,应该没有较大的问题


by SpeedStar @ 2023-05-04 15:00:04

@Benzenesir 我猜是你的dfs写炸了


by Benzenesir @ 2023-05-04 15:14:47

@寒烟冷浅暮殇 fix,thx


|