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 luqyou @ 2023-12-25 18:39:35

@Industrial_banana 昨天下午已经调出来了,感谢


上一页 |