dinic求助

珈乐唯毒 @ 2020-07-08 09:37:52

#include<bits/stdc++.h>
using namespace std;
const long long N=205,M=5005,INF=LLONG_MAX;
long long head[N],en=1;
struct Edge{
    long long next,to,from,val;
}edge[M*2];
void add(long long from,long long to,long long val){
    edge[++en].to=to;
    edge[en].next=head[from];
    edge[en].val=val;
    head[from]=en;
    return;
} 
long long n,m,s,t;
long long ans;
long long dep[N];
queue<long long> q;
bool bfs(){
    memset(dep,0,sizeof(dep));
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        long long u=q.front();
        q.pop();
        for(long long i=head[u];i;i=edge[i].next){
            if(!edge[i].val||dep[edge[i].to])continue;
            long long v=edge[i].to;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
    return dep[t]!=0;
}
long long dfs(long long u,long long flow){
    if(u==t)return flow;
    long long ans=0;
    for(long long i=head[u];i;i=edge[i].next){
        if(!edge[i].val||dep[edge[i].to]!=dep[u]+1)continue;
        long long v=edge[i].to;
        long long rst=dfs(v,min(flow-ans,edge[i].val));
        ans+=rst;
        edge[i].val-=rst;
        edge[i^1].val+=rst;
        if(ans==flow)break;
    }
    return ans;
}
long long dinic(){
    long long ans=0;
    while(bfs()){
        long long rst=dfs(s,INF);
        if(!rst)return ans;
        ans+=rst;
    }
    return ans;
}
int main(){
    cin>>n>>m>>s>>t;
    for(long long i=1;i<=m;i++){
        long long u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add(v,u,0);
        add(u,v,w);
    }
    cout<<dinic();
    return 0;
} 

by 杀仁犯 @ 2020-07-08 11:04:13

你这个没写弧优化，这样写就行了

#include<bits/stdc++.h>
using namespace std;
const long long N=205,M=5005,INF=LLONG_MAX;
long long head[N],cur[N],en=1;
struct Edge{
    long long next,to,from,val;
}edge[M*2];
void add(long long from,long long to,long long val){
    edge[++en].to=to;
    edge[en].next=head[from];
    edge[en].val=val;
    head[from]=en;
    cur[from]=en;
    return;
} 
long long n,m,s,t;
long long ans;
long long dep[N];
queue<long long> q;
bool bfs(){
    memset(dep,0,sizeof(dep));
    for(int i=1;i<=n;i++)cur[i]=head[i];
    q.push(s);
    dep[s]=1;
    while(!q.empty()){
        long long u=q.front();
        q.pop();
        for(long long i=head[u];i;i=edge[i].next){
            if(!edge[i].val||dep[edge[i].to])continue;
            long long v=edge[i].to;
            dep[v]=dep[u]+1;
            q.push(v);
        }
    }
    return dep[t]!=0;
}
long long dfs(long long u,long long flow){
    if(u==t)return flow;
    long long ans=0;
    for(long long i=cur[u];i;i=edge[i].next){
        cur[u]=i;
        if(!edge[i].val||dep[edge[i].to]!=dep[u]+1)continue;
        long long v=edge[i].to;
        long long rst=dfs(v,min(flow-ans,edge[i].val));
        ans+=rst;
        edge[i].val-=rst;
        edge[i^1].val+=rst;
        if(ans==flow)break;
    }
    return ans;
}
long long dinic(){
    long long ans=0;
    while(bfs()){
        long long rst=dfs(s,INF);
        if(!rst)return ans;
        ans+=rst;
    }
    return ans;
}
int main(){
    cin>>n>>m>>s>>t;
    for(long long i=1;i<=m;i++){
        long long u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add(v,u,0);
        add(u,v,w);
    }
    cout<<dinic();
    return 0;
} 

by 珈乐唯毒 @ 2020-07-08 11:04:55

@杀仁犯 谢谢大佬，Orz

by pyqpyq @ 2020-07-15 08:57:08

蓝名神仙orz