dinic算法16分求救！！！

Ming3398 @ 2024-10-05 10:19:50

#include<iostream>
#include<queue>
#include<cstring>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;int n,m,s,t;
const int N=210,M=1e4+10;
int h[N],to[M],w[M],ne[M],idx;
int dep[N],now[N];
void add(int a,int b,int c){
    to[++idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;
}
bool bfs(){
    memset(dep,0x3f,sizeof dep);
    queue<int> q;q.push(s);dep[s]=0;now[s]=h[s];
    while(q.size()){
        int tmp=q.front();q.pop();
        for(int i=h[tmp];i;i=ne[i]){
            int j=to[i];
            if(dep[j]==inf&&w[i]>0){
                dep[j]=dep[tmp]+1;
                now[j]=h[j];
                q.push(j);
                if(j==t) return 1;
            }
        }
    }
    return 0;
}
ll dfs(ll u,ll sum){
    //cout<<u<<" ";
    if(u==t) return sum;
    ll flow=0;
    for(int i=now[u];i&&sum>0;i=ne[i]){
        int j=to[i];
        now[u]=i;
        if((dep[j]==dep[u]+1)&&w[i]>0){
            ll k=dfs(j,min(sum,(ll)w[i]));
            if(!k) w[i]=inf;
            w[i]-=k;w[i^1]+=k;
            flow+=k;
            sum-=k;
        }
    }
    return flow;
}
void dinic(){
    ll ans=0;
    while(bfs()) ans+=dfs(s,inf);
    cout<<ans<<endl;
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        add(a,b,c);add(b,a,0);
    }
    dinic();
    return 0;
}

by Ming3398 @ 2024-10-06 10:36:55

#include<iostream>
#include<queue>
#include<cstring>
#define ll long long
#define inf 0x3f3f3f3f
using namespace std;int n,m,s,t;
const int N=210,M=1e4+10;
int h[N],to[M],w[M],ne[M],idx;
int dep[N],now[N];
void add(int a,int b,int c){
    to[++idx]=b;w[idx]=c;ne[idx]=h[a];h[a]=idx;
}
bool bfs(){
    memset(dep,0x3f,sizeof dep);
    queue<int> q;q.push(s);dep[s]=0;now[s]=h[s];
    while(q.size()){
        int tmp=q.front();q.pop();
        for(int i=h[tmp];i;i=ne[i]){
            int j=to[i];
            if(dep[j]==inf&&w[i]>0){
                dep[j]=dep[tmp]+1;
                now[j]=h[j];
                q.push(j);
                if(j==t) return 1;
            }
        }
    }
    return 0;
}
ll dfs(ll u,ll sum){
    //cout<<u<<" ";
    if(u==t) return sum;
    ll flow=0;
    for(int i=now[u];i&&sum>0;i=ne[i]){
        int j=to[i];
        now[u]=i;
        if((dep[j]==dep[u]+1)&&w[i]>0){
            ll k=dfs(j,min(sum,(ll)w[i]));
            if(!k) dep[j]=inf;
            w[i]-=k;w[i^1]+=k;
            flow+=k;
            sum-=k;
        }
    }
    return flow;
}
void dinic(){
    ll ans=0;
    while(bfs()) ans+=dfs(s,inf);
    cout<<ans<<endl;
}
int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int a,b,c;cin>>a>>b>>c;
        add(a,b,c);add(b,a,0);
    }
    dinic();
    return 0;
}

32分了