dinic算法91分 第9个点莫名其妙TLE 求调

P3376 【模板】网络最大流

scyFBM @ 2023-01-11 16:13:30

rt,代码是老师发的板子与第三篇题解的杂交版

评测记录

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=209;
const int M=5009;
int n,m,s,t;
int dis[N];
struct edge{
    int l,r,c;
    int nxt;
}e[M*2];
int hed[N],ecnt=2;
void add(int l,int r,int c){
    e[ecnt].l=l;
    e[ecnt].r=r;
    e[ecnt].c=c; 
    e[ecnt].nxt=hed[l];
    hed[l]=ecnt;
    ecnt++; 
}
bool bfs(){
    queue<int> q;
    for(int i=1;i<=n;i++) dis[i]=-1;
    dis[s]=0;
    q.push(s);
    while(!q.empty()){
        int cur=q.front();
        q.pop();
        for(int i=hed[cur];i;i=e[i].nxt){
            if(dis[e[i].r]==-1&&e[i].c>0){
                dis[e[i].r]=dis[cur]+1;  
                q.push(e[i].r);
            }
        }
    }
    return(dis[t]!=-1);
}
int dfs(int start,int flow){
    int cnt=0; 
    if(start==t) return flow;
    for(int i=hed[start];i&&flow;i=e[i].nxt){ 
        if((e[i].c>0)&&(dis[e[i].r]==dis[start]+1)){
            int ret=dfs(e[i].r,min(flow,e[i].c)); 
            if(ret>0){
                e[i].c-=ret; 
                if(i&1) e[i-1].c+=ret;
                else e[i+1].c+=ret;
                cnt+=ret;
                flow-=ret; 
            }
        }
    }   
    return cnt; 
}
signed main(){
    cin>>n>>m>>s>>t;
    for(int i=0;i<m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0);
    }
    int ans=0;
    while(bfs()) ans+=dfs(s,1e9);
    cout<<ans<<endl;
    return 0;
}

by scyFBM @ 2023-01-11 17:29:06

@JR_ytxy 谢谢奆佬


by scyFBM @ 2023-01-11 18:46:04

过了 蟹蟹大家


by Jeefy @ 2023-01-14 14:48:31

没有吧,我没加当前弧优化也可以过的

详见:记录详情


上一页 |