为什么ek跑的2 , 9 , 10 mle了,好像没啥问题呀0.0

P3376 【模板】网络最大流

zixi @ 2019-08-09 11:03:11

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e4+10;
const int inf=0x3f3f3f3f;
int n,m,s,t;
int liu[maxn][maxn],rong[maxn][maxn];
int p[maxn],pre[maxn];
int maxsum;

void inter(){
    queue<int>st;
    while(1){
        memset(p,0,sizeof(p));
        p[s]=inf;
        st.push(s);
        while(!st.empty()){
            int ans=st.front();st.pop();
            for(int i=1;i<=n;i++){
                if(!p[i]&&rong[ans][i]>liu[ans][i]){
                    p[i]=min(p[ans],rong[ans][i]-liu[ans][i]);
                    pre[i]=ans;
                    st.push(i);
                }
            }
        }
        if(!p[t]){
            break;
        }
        maxsum+=p[t];
        int temp=t;
        while(pre[temp]){
            liu[pre[temp]][temp]+=p[t];
            liu[temp][pre[temp]]-=p[t];
            temp=pre[temp];
        }
    }
}
int main()
{
    cin>>n>>m>>s>>t;
    int x,y,z;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        rong[x][y]+=z;
    }
    inter();
    cout<<maxsum<<endl;
}

by 挪威的森林 @ 2019-09-23 11:22:28

这个东西算法复杂度太大了,数组1e8也开不下啊。


|