求助

P3376 【模板】网络最大流

Tx_Lcy @ 2022-08-13 11:28:09

这个题卡 \verb!EK!?我的 \verb!EK TLE! 了两个点,是我的写法有问题吗。

#include<bits/stdc++.h>
#define int long long
#define rint register int
using namespace std;
int const N=2e2+10;
int const M=1e6+10;
int pre[N],b[N],n,m,head[M],cnt=1,flag[N][N];
struct node{int to,nxt,val;}a[M];
inline void add_edge(int u,int v,int w){
    a[++cnt].to=v,a[cnt].val=w,a[cnt].nxt=head[u];
    head[u]=cnt,
    a[++cnt].to=u,a[cnt].val=0,a[cnt].nxt=head[v],
    head[v]=cnt;
}
inline int EK(int s,int t){
    int flow=0;
    while (1){
        for (rint i=1;i<=n;i++) b[i]=0;
        queue<int>q;q.push(s),b[s]=1;
        int now_flow=1e9;
        while (!q.empty()){
            int now=q.front();q.pop();
            for (rint i=head[now];i;i=a[i].nxt){
                int v=a[i].to;
                if (a[i].val==0) continue;
                if (b[v]) continue;
                pre[v]=i,q.push(v);b[v]=1;
                now_flow=min(now_flow,a[i].val);
                if (v==t) break;
            }
        }
        if (!b[t]) break;
        flow+=now_flow;int now=t;
        while (now!=s){
            a[pre[now]].val-=now_flow,
            a[pre[now]^1].val+=now_flow,
            now=a[pre[now]^1].to;
        }
    }
    return flow;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int s,t,u,v,w;cin>>n>>m>>s>>t;
    while (m--){
        cin>>u>>v>>w;
        if (flag[u][v]==0) add_edge(u,v,w),flag[u][v]=cnt;
        else a[flag[u][v]-1].val+=w;
    }
    cout<<EK(s,t)<<'\n';
    return 0;
}

|