最大流库

使用 Dinic 实现，支持输出最小割。

#include<iostream>
#ifndef DINIC_HPP

#include<vector>
#include<queue>
#include<algorithm>
#include<limits>

namespace _dinic{

namespace __detail{

using size_t=long long;

template<size_t Node_cnt,typename Flow_type=long long>
class dinic{
    struct ed_t{
        bool isori;
        size_t v,rid;
        Flow_type flo;
    };
    std::vector<ed_t> *ed;
    size_t _S,_T;
    Flow_type _ans;
    size_t *lev,*cur;
    size_t _ncnt;
    bool _bfs(){
        std::fill(lev,lev+_ncnt+1,-1);
        lev[_S]=1;
        std::queue<size_t> que;
        que.push(_S);
        while(!que.empty()){
            size_t u=que.front();
            que.pop();
            for(auto &e:ed[u]){
                if(e.flo==0) continue;
                if(lev[e.v]==-1){
                    lev[e.v]=lev[u]+1;
                    que.push(e.v);
                }
            }
        }
        return lev[_T]!=-1;
    }
    Flow_type _dfs(size_t it,Flow_type tflo){
        if(it==_T) return tflo;
        Flow_type rest=tflo;
        for(size_t &i=cur[it];i<(size_t)ed[it].size();++i){
            auto &e=ed[it][i];
            if(e.flo==0||lev[e.v]!=lev[it]+1) continue;
            Flow_type rec=_dfs(e.v,std::min(rest,e.flo));
            if(rec==0){
                lev[e.v]=-1;
            }else{
                e.flo-=rec;
                rest-=rec;
                ed[e.v][e.rid].flo+=rec;
                if(rest==0) break;
            }
        }
        return tflo-rest;
    }
public:
    dinic(int S,int T):
        ed(new std::vector<ed_t>[Node_cnt+1]),
        _S(S),_T(T),_ans(0),
        lev(new size_t[Node_cnt+1]),
        cur(new size_t[Node_cnt+1]),
        _ncnt(0){}
    dinic(const dinic &o)=delete;
    dinic &operator=(const dinic &o)=delete;
    dinic(dinic &&o)=delete;
    ~dinic(){
        delete[] ed;
        delete[] lev;
        delete[] cur;
    }
    void add_edge(size_t u,size_t v,Flow_type flo){
        ed_t fo{true,v,(size_t)ed[v].size(),flo},ba{false,u,(size_t)ed[u].size(),0};
        ed[u].push_back(fo);
        ed[v].push_back(ba);
        if(_ncnt<u) _ncnt=u;
        if(_ncnt<v) _ncnt=v;
        return ;
    }
    Flow_type max_flow(){
        while(_bfs()){
            std::fill(cur,cur+_ncnt+1,0);
            _ans+=_dfs(_S,std::numeric_limits<Flow_type>::max());
        }
        return _ans;
    }
    std::vector<std::pair<size_t,size_t> > get_min_cut(){
        std::vector<std::pair<size_t,size_t> > ret;
        for(size_t i=1;i<=_ncnt;++i){
            for(auto &e:ed[i]){
                if(e.isori&&e.flo==0){
                    ret.push_back(std::make_pair(i,e.v));
                }
            }
        }
        return ret;
    }
};

} //namespace __detail

using __detail::dinic;

}//namespace _dinic

#endif // DINIC_HPP
#include<iostream>
using namespace std;
constexpr int MAXN=200,MAXM=500;
int N=0,M=0,S=0,T=0;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin>>N>>M>>S>>T;
    _dinic::dinic<MAXN> G(S,T);
    for(int i=1;i<=M;i++){
        int u,v,flo;
        cin>>u>>v>>flo;
        G.add_edge(u,v,flo);
    }
    cout<<G.max_flow()<<endl;
    return 0;
}

费用流库

使用 SPFA + EK 实现。

#include<iostream>
#include<vector>
#include<limits>
#include<deque>
template<int NSIZ,typename Flow_t,typename Cost_t,typename Comp=std::less<Cost_t> >
class min_cost_max_flow_t{
    static Cost_t min(const Cost_t &a,const Cost_t &b){return Comp()(b,a)?b:a;}
    static bool tomin(Cost_t &a,const Cost_t &b){if(Comp()(b,a)){a=b; return 1;} return 0;}
    struct ed_t{
        int v,r; Flow_t f; Cost_t c;
        bool operator>(const ed_t &o)const{
            return Comp()(o.c,c);
        }
    };
    int ncnt;
    std::vector<std::vector<ed_t> > ed;
    std::vector<char> vis;
    std::vector<Cost_t> dis;
    std::vector<Flow_t> Flow;
    std::vector<int> rev;
    std::deque<int> dque;
    std::vector<char> in;
    void upd(){
        if(dque.size()>=2){
            if(Comp()(dis[dque.back()],dis[dque.front()]))
                std::swap(dque.front(),dque.back());
        }
        return ;
    }
    void spfa(int S){
        std::fill(vis.begin(),vis.begin()+ncnt+1,0);
        std::fill(Flow.begin(),Flow.begin()+ncnt+1,0);
        std::fill(rev.begin(),rev.begin()+ncnt+1,-1);
        dis[S]=0; Flow[S]=std::numeric_limits<Flow_t>::max();
        vis[S]=1; dque.push_back(S); in[S]=1;
        while(!dque.empty()){
            int it=dque.front(); dque.pop_front(); in[it]=0;
            upd();
            for(auto e:ed[it])if(e.f>0){
                if((!vis[e.v])||Comp()(dis[it]+e.c,dis[e.v])){
                    dis[e.v]=dis[it]+e.c;
                    vis[e.v]=1;
                    Flow[e.v]=std::min(Flow[it],e.f);
                    rev[e.v]=e.r;
                    if(!in[e.v]){
                        dque.push_back(e.v); in[e.v]=1;
                        upd();
                    }
                }
            }
        }
        return ;
    }
public:
    min_cost_max_flow_t():ncnt(0),ed(NSIZ+1),vis(NSIZ+1),
        dis(NSIZ+1),Flow(NSIZ+1),rev(NSIZ+1),in(NSIZ+1){}
    void connect(int u,int v,Flow_t f,Cost_t c){
        if(ncnt<u) ncnt=u;
        if(ncnt<v) ncnt=v;
        int usiz=ed[u].size(),vsiz=ed[v].size();
        ed[u].push_back({v,vsiz,f,c});
        ed[v].push_back({u,usiz,0,-c});
        return ;
    }
    std::pair<Flow_t,Cost_t> maxflow(int S,int T){
        Flow_t flow=0; Cost_t cost=0;
        while(1){
            spfa(S);
            if(rev[T]==-1) break;
            Flow_t f=Flow[T];
            flow+=f;
            for(int it=T;rev[it]!=-1;){
                auto &re=ed[it][rev[it]];
                auto &e=ed[re.v][re.r];
                cost+=e.c*f;
                e.f-=f;
                re.f+=f;
                it=re.v;
            }
        }
        return {flow,cost};
    }
};
using ll=long long;
constexpr int MAXN=5e3,MAXM=5e4;
int main(){
    min_cost_max_flow_t<MAXN,ll,ll> G;
    using std::cin; using std::cout;
    int n,m,s,t; cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        int u,v,w,c; cin>>u>>v>>w>>c;
        G.connect(u,v,w,c);
    }
    auto pi=G.maxflow(s,t);
    cout<<pi.first<<' '<<pi.second<<'\n';
    return 0;
}