MnZn刚学网络瘤,EK算法全部TLE+RE求助

P3376 【模板】网络最大流

charleshe @ 2023-02-11 17:17:15

#include <iostream>
#include <queue>
#define int long long
using namespace std;
struct edge{
    int v,w,nxt;
};
edge e[5005];
int h[202];
int cnt=1;
void add(int u,int v,int w){
    e[++cnt].v=v;
    e[cnt].w=w;
    e[cnt].nxt=h[u];
    h[u]=cnt;
}
int n,m,s,t;
int lst[202];
int flw[202];
int flg[202][202];
bool bfs(){
    for(int i=1;i<=n;i++) lst[i]=-1;
    queue<int> q;
    q.push(s);
    flw[s]=1ll<<60;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(u==t) break;
        for(int i=h[u];i;i=e[i].nxt){
            int v=e[i].v,w=e[i].w;
            if(w>0&&lst[v]==-1){
                lst[v]=u;
                flw[v]=min(flw[u],w);
                q.push(v);
            }
        }
    }
    return lst[t]>-1;
}
int EK(){
    int maxf=0;
    while(bfs()){
        maxf+=flw[t];
        for(int i=t;i!=s;i=e[lst[i]^1].v){
//          cout<<e[i].v<<" "<<e[i].w<<" "<<endl;
            e[lst[i]].w-=flw[t];
            e[lst[i]^1].w+=flw[t];
        }
    }
    return maxf;
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        if(!flg[u][v]){
            add(u,v,w);
            add(v,u,0);
//          cout<<u<<" "<<v<<" "<<w<<endl;
            flg[u][v]=cnt;
        }
        else e[flg[u][v]-1].w+=w;
    }
//  for(int i=1;i<=n;i++){
//      for(int j=h[i];j;j=e[j].nxt) cout<<i<<" "<<e[i].v<<" "<<e[j].w<<endl;
//  }
    cout<<EK()<<endl;
    return 0;
}

写错了轻喷

差不多是照着这个写的


by ducati @ 2023-02-11 17:22:46

@charleshe 一共最多 5000 条边,加上反向边一共有 10^4 条,但你的 edge 数组只开了 5000


by charleshe @ 2023-02-11 17:24:10

@ducati 现在是全T力(悲


by ducati @ 2023-02-11 17:32:42

@charleshe 是的,但我看了一会儿也不知道为什么会全 T。感觉看不出什么问题 /kk


by charleshe @ 2023-02-11 17:38:29

艹,一处i打成了u导致的问题,已经过了

此贴完结


|