请求加强数据

P3376 【模板】网络最大流

lao_wang @ 2024-05-06 15:50:28

我的代码

bool bfs(){
    for(int i=1;i<=n;i++) now[i] = head[i] , dep[i] = 0x3f3f3f3f3f3f , vis[i] = 0 ;
    q.push(s) ;
    dep[s] = 0 ;
    while(!q.empty()){
        int u=q.front() ;
        q.pop() ;
        vis[u] = 0 ;
        for(int i=head[u];~i;i=G[i].next){
            int x=G[i].to ;
            if(dep[x]<=dep[u]+1||!G[i].w) continue ;
            dep[x] = dep[u]+1 ;
            if(!vis[x]){
                vis[x] = 1 ;
                q.push(x) ;
            }
        }
    }
    return dep[t]!=0x3f3f3f3f3f3f ;
}
int dfs(int u,int minn){
    if(u==t){ vis[u]=1 ;return minn ; }
    if(vis[u]) return 0 ;
    vis[u] = 1 ;
    int use=0 ;
    for(int i=now[u];~i;i=G[i].next){
        now[u] = i ;
        int x=G[i].to ;
        if(!G[i].w||dep[x]!=dep[u]+1) continue ;
        int temp = dfs(x,min(minn,G[i].w)) ;
        if(!temp) continue ;
        G[i].w -= temp ;
        G[i^1].w += temp ;
        use += temp ;
        if(use==minn) break; 
    }
    return use ;
}
int dinic(){
    long long ans=0 ;
    while(bfs()){
            int temp=dfs(s,2147483647) ;
            ans += temp ;
    }
    return ans ;
}

其中 dfs(x,min(minn,G[i].w)) 原本应该为 dfs(x,min(minn-use,G[i].w)) 但是他过了…………


by lao_wang @ 2024-05-06 15:54:39

@chen_zhe (找不到该@哪个管理员)


by WydnksqhbD @ 2024-05-06 16:09:32

@lao_wang 题目管理


by lao_wang @ 2024-05-06 16:10:16

@WydnksqhbD 没有,找过了没更新


by WydnksqhbD @ 2024-05-06 16:11:07

@lao_wang 哦……


by tjx114514 @ 2024-05-06 16:18:07

太认真了


by qzmoot @ 2024-05-06 16:42:47

@lao_wang 扶苏?


by lao_wang @ 2024-05-09 15:48:19

@Maxmilite


by Maxmilite @ 2024-05-10 21:13:41

我们没太有时间仔细研究每个题该如何加强数据,如果想要加强数据,还烦请提供一份数据或数据生成器


by Otue @ 2024-05-14 16:56:07

@lao_wang 你这个代码本来就不存在正确性问题。而且这个优化可加可不加。


by lao_wang @ 2024-05-14 16:59:03

@stOtue ?有道题目这种写法过不了:https://www.luogu.com.cn/problem/P4313


| 下一页