网络流模板

Dinic

const int maxn = 50000+50;
const int maxm = 200000+200;
#define Ci const int &
int n,m,s,t;
struct edge{
    int u,v,n,flow;
    I edge(Ci _u=0,Ci _v=0,Ci _n=0,Ci _flow=0):u(_u),v(_v),n(_n),flow(_flow){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn];
I void add(Ci u,Ci v,Ci flow){
    e[++cnt]=edge(u,v,head[u],flow),head[u]=cnt;
    e[++cnt]=edge(v,u,head[v],0),head[v]=cnt;
}
int dep[maxn];
I bool bfs(){
    queue<int>q;
    memset(dep,0,sizeof dep);
    memcpy(cur,head,sizeof(head));
    dep[s]=1,q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
            if(e[ee].flow&&dep[v]==0)
                dep[v]=dep[u]+1,q.push(v);
    }
    return dep[t];
}
int dfs(int u,int limit){
    if(limit==0||u==t)return limit;
    int flow=0,f;
    for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
        if(dep[v]==dep[u]+1&&(f=dfs(v,min(limit,e[ee].flow)))){
            flow+=f;
            limit-=f;
            e[ee].flow-=f;
            e[ee^1].flow+=f;
            if(!limit)break;
        }
    return flow;
}
I int dinic(){
    int ans=0;
    while(bfs())
            ans+=dfs(s,inf);
        return ans;
}
signed main(){
    read(n),read(m),read(s),read(t);
    int u,v,f;
    FOR(i,1,m)
        read(u),read(v),read(f),
        add(u,v,f);
    write(dinic());
    flush();
    return 0;
}

ISAP

int tot,s,t;
const int maxn = 50000+50;
const int maxm = 200000+200;
#define ci const int &
struct edge{
    int u,v,f,n;
    I edge(ci uu =0,ci vv=0,ci ff=0,ci nn=0):u(uu),v(vv),f(ff),n(nn){}
}e[maxm];
int cnt=1,head[maxn],cur[maxn],gap[maxn],dis[maxn];
I void add(ci u,ci v,ci f){
    e[++cnt]=edge(u,v,f,head[u]),head[u]=cnt;
    e[++cnt]=edge(v,u,0,head[v]),head[v]=cnt;
}
I void bfs(){
    // memset(dis,0,sizeof dis);
    // memset(gap,0,sizeof gap);
    queue<int>q;q.push(t),gap[dis[t]=1]++;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
        if(!dis[v])gap[dis[v]=dis[u]+1]++,q.push(v);
    }
}
int dfs(ci u,ci flow){
    if(u==t)return flow;
    int us=0,f;
    for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
        if(dis[v]==dis[u]-1){
            if(f=dfs(v,min(flow-us,e[ee].f)))
                e[ee].f-=f,e[ee^1].f+=f,us+=f;
            if(us==flow)return flow;
        }
    (--gap[dis[u]])?(++gap[++dis[u]]):dis[s]=tot+1;
    return us;
}
I int isap(){
    int ans=0;
    bfs();
    while(dis[s]<=tot+1)
        memcpy(cur,head,sizeof head),
        ans+=dfs(s,inf);
    return ans;
}
int n,m;
signed main(){
    int u,v,f;
    read(n),read(m),read(s),read(t);
    tot=n;
    FOR(i,1,m)read(u),read(v),read(f),add(u,v,f);
    write(isap());
    flush();
    return 0;
}

费用流

const int maxn = 50000+500;
const int maxm = 200000+2000;
#define ci const int &
struct edge{
    int u,v,f,w,n;
    I edge(ci uu=0,ci vv=0,ci ff=0,ci ww=0,ci nn=0):u(uu),v(vv),f(ff),w(ww),n(nn){}
}e[maxm];
int dis[maxn],vis[maxn],cur[maxn],head[maxn],cnt=1,n,m,s,t;
int cost=0,flow=0;
I void add(ci u,ci v,ci f,ci w){
    e[++cnt]=edge(u,v,f,w,head[u]),head[u]=cnt;
    e[++cnt]=edge(v,u,0,-w,head[v]),head[v]=cnt;
}
I bool spfa(ci s,ci t){
    memset(vis,0,sizeof vis);
    memset(dis,0x3f,sizeof dis);
    deque<int>q;q.push_front(t);
    vis[t]=1,dis[t]=0;
    while(!q.empty()){
        int u=q.front();q.pop_front();
        for(int ee=head[u],v;v=e[ee].v,ee;ee=e[ee].n)
            if(e[ee^1].f>0&&dis[v]>dis[u]-e[ee].w){
                dis[v]=dis[u]-e[ee].w;
                if(!vis[v])vis[v]=1,(!q.empty()&&dis[q.front()]>dis[v])?
                q.push_front(v):
                q.push_back(v);
            }
        vis[u]=0;
    }
    return dis[s]==0x3f3f3f3f?0:1;
}
int dfs(ci u,ci ff){
    if(u==t)return vis[t]=1,ff;
    int us=0,f;vis[u]=1;
    for(int ee=cur[u],v;cur[u]=ee,v=e[ee].v,ee;ee=e[ee].n)
        if(vis[v]==0&&e[ee].f>0&&dis[u]-e[ee].w==dis[v]){
            if((f=dfs(v,min(e[ee].f,ff-us)))>0)
                cost+=f*e[ee].w,e[ee].f-=f,e[ee^1].f+=f,us+=f;
            if(us==ff)break;
        }
    return us;
}
I void cost_flow(){
    while(spfa(s,t)){
        vis[t]=1;
        while(vis[t]){
            memcpy(cur,head,sizeof head);
            memset(vis,0,sizeof vis);
            flow+=dfs(s,inf);
        }
    }
}
signed main(){
    read(n),read(m),read(s),read(t);
    int u,v,f,w;
    FOR(i,1,m)
        read(u),read(v),read(f),read(w),
        add(u,v,f,w);
    cost_flow();
    write(flow),pc(' '),write(cost);
    flush();
    return 0;
}