Dinic 样例死循环求调

P3376 【模板】网络最大流

luqyou @ 2023-12-24 11:53:03

RT

#include<bits/stdc++.h>
//#include<windows.h>
using namespace std;
const int maxn=200+10,maxm=5000+10;
const int inf=2147483647;
struct edge{
    int v,w;
}e[maxm*2];
int n,m,cnt=1,s,t,cur[maxn],d[maxn];
vector<int> G[maxn];
queue<int> q;
void adde(int u,int v,int w){
    e[++cnt]={v,w};
    G[u].push_back(cnt);
} 
bool bfs(int s){
    memset(d,0,sizeof d);
    q.push(s);
    d[s]=1;
    while(q.size()){
        int u=q.front();
        q.pop();
//      cout<<u<<endl; 
        for(int x:G[u]){
            int v=e[x].v;
//          cout<<u<<"->"<<v<<endl;
//          Sleep(100);
            if(d[v]==0&&e[x].w>0){
//              cout<<u<<" "<<v<<" "<<e[x].w<<endl;
//              cout<<u<<"->"<<v<<endl;
                d[v]=d[u]+1;
//              cout<<d[v]<<endl;
                q.push(v);
                if(v==t){
                    return 1;
                } 
            }
        }
    }
    return 0;
}
int dfs(int u,int nf){
    if(u==t) return nf;
    int k,res=0;
    for(int i=cur[u];i<G[u].size();i++){
        int x=G[u][i];
        cur[u]=i;
        if(e[x].w>0&&d[u]+1==d[e[x].v]){
            k=dfs(e[x].v,min(nf,e[x].w));
            e[x].w-=k;
            e[x^1].w+=k;
            res+=k;
            nf-=k; 
            if(nf==0) break;
        }
    } 
    return res;
} 
int dinic(int s){
    memset(cur,0,sizeof cur);
    int res=0; 
    while(bfs(s)){
        res+=dfs(s,inf);
//      cout<<endl;
//      cout<<"------"<<endl;
//      system("cls");
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        adde(u,v,w);
        adde(v,u,0); 
    }
    cout<<dinic(s);
    return 0;
}

by vzcx_host @ 2023-12-24 11:58:29

当前弧优化要求每次 dfs 之前都要重置 cur 数组


by luqyou @ 2023-12-24 11:59:45

@Industrial_banana 改了,貌似还是死循环


by DANNNqwq @ 2023-12-24 12:14:59

dinic函数应该这么写

ll dinic() {
    ll res=0;
    while(bfs()) {
        for(int i=1;i<=n;i++) cur[i]=head[i];
        ll flow;
        while(flow=dfs(s,INF)) res+=flow;
    }
    return res;
}

by DANNNqwq @ 2023-12-24 12:16:20

@luqyou


by DANNNqwq @ 2023-12-24 12:20:04

在dfs函数中

k=dfs(e[x].v,min(nf,e[x].w));

应写成

k=dfs(e[x].v,min(res,e[x].w));

by luqyou @ 2023-12-24 12:25:58

@DANNNsth 改了,but还是死循环


by DANNNqwq @ 2023-12-24 12:37:45

在dfs函数中 for(int i=cur[u];i<G[u].size();i++){应该为for(int i=cur[u];i<G[u].size()&&nf;i++){


by luqyou @ 2023-12-24 14:42:10

@DANNNsth for循环里面有判if(nf==0) break;


by vzcx_host @ 2023-12-25 10:35:42

@luqyou 等一下


by vzcx_host @ 2023-12-25 10:36:11

@luqyou 你 bfs 时 q 没清


| 下一页