友情链接:
【图论】网络流问题——最大流入门(Dinic算法)
【图论】最小费用最大流(网络流进阶)

一、最大流:dinic算法最终优化模板

测试OJ:
LOJ #101. 最大流 27~30 ms
洛谷 P3376 【模板】网络最大流 65~100 ms

建议点数和边数可以开大一点,开到1e5,防止建图的时候没算好边和点数而导致TLE。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=210,M=5010;
const ll inf=(1ll<<63)-1;
int s,t,cnt,head[N],dep[N],cur[N];
struct node
{
    int to,next;
    ll w;
}e[M<<1];
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
}
void add(int x,int y,ll z)
{
    e[cnt].to=y;
    e[cnt].w=z;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x,int y,ll z)
{
    add(x,y,z);
    add(y,x,0);
}
bool bfs() // 广度遍历,形成分层图
{
     queue<int>q;
     while(!q.empty())q.pop();
     q.push(s);
     memset(dep,0,sizeof(dep));
     dep[s]=1; // 起点在第1层
     while(!q.empty())
     {
         int u=q.front();q.pop();
         for(int i=head[u];~i;i=e[i].next)
         {
             int v=e[i].to;
             if(e[i].w>0&&dep[v]==0)
             {
                 dep[v]=dep[u]+1;
                 q.push(v);
             }
         }
     }
     return dep[t];
}
// 除了源点和汇点,其他所有点的流入量=流出量,将其称为"流量"
// dfs函数返回残留网络中u点到汇点的流量
ll dfs(int u,ll in) // in是u点的最大流入量(不一定都被用完,搜完u点以后的路径才知道流出多少)
{
    if(u==t||in==0)return in;
    ll out=0; // out表示u点的实际流出量,初始化为0
    for(int &i=cur[u];~i;i=e[i].next) // cur[u]当前弧优化
    {
        int v=e[i].to;
        if(e[i].w&&dep[u]+1==dep[v])
        {
            ll res=dfs(v,min(in,e[i].w)); // 从源点到u点的最大流量受路上最小容量的限制
            // res得到的是u点的最大流出量(u->v,边的容量为e[i].w)
            e[i].w-=res;
            e[i^1].w+=res;
            in-=res;
            out+=res;
            if(in==0)break; // 流入量都被用完了。一定要加这句话,否则超时!
        }
    }
    if(out==0)dep[u]=0; // u点没有搜出增广路来流出流量,下次不再搜它了
    return out;
}
ll dinic()
{
    ll sum=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(head));
        while(ll d=dfs(s,inf))
            sum+=d;
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    int n,m,x,y,z;
    cin>>n>>m>>s>>t;
    init();
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>z;
        add_edge(x,y,z);
    }
    ll ans=dinic();
    printf("%lld\n",ans);
    return 0;
}

二、费用流:dinic算法最终优化模板

测试OJ:
LOJ #102. 最小费用流 1927ms
洛谷 P3381 【模板】最小费用最大流 1882ms

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5010,M=50010;
const ll inf=(1ll<<63)-1;
int n,m,s,t,cnt,head[N],cur[N];
ll dis[N],mincost;
bool vis[N];
struct node
{
    int to,next;
    ll w,cost;  // 容量w 单位流量花费cost
}e[M<<1];
void init()
{
    memset(head,-1,sizeof(head));
    cnt=0;
    mincost=0;
}
void add(int x,int y,ll w,ll cost)
{
    e[cnt].to=y;
    e[cnt].w=w;
    e[cnt].cost=cost;
    e[cnt].next=head[x];
    head[x]=cnt++;
}
void add_edge(int x, int y, ll w, ll cost)
{
    add(x,y,w,cost);
    add(y,x,0,-cost);
}
bool spfa()
{
    queue<int>q;
    while(!q.empty())q.pop();
    for (int i=1;i<=n;i++)
        dis[i]=inf;
    dis[s]=0;
    memset(vis,0,sizeof(vis));
    q.push(s);
    vis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        vis[u]=0;
        for(int i=head[u];~i;i=e[i].next)
        {
            int v=e[i].to;
            if(e[i].w&&dis[u]+e[i].cost<dis[v]) // 分清楚dis的含义是求cost的最短路
            {
                dis[v]=dis[u]+e[i].cost;
                if(!vis[v])
                {
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return dis[t]!=inf;
}
ll dfs(int u,ll in)
{
    if(u==t||in==0)return in;
    vis[u]=1; // 这里很重要,标记这个点被走过了,防止可能有环导致死循环
    ll out=0;
    for(int &i=cur[u];~i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[u]+e[i].cost==dis[v]&&e[i].w&&!vis[v]) 
        // 在LOJ中测试,发现如果先判断dis[u]+e[i].cost==dis[v]会快200ms
        // 但是在洛谷中测试,没什么区别
        {
            ll res=dfs(v,min(in,e[i].w));
            e[i].w-=res;
            e[i^1].w+=res;
            in-=res;
            out+=res;
            mincost+=e[i].cost*res;
            if(in==0)break;
        }
    }
    vis[u]=0; // 还原标记
    if(out==0)vis[u]=1;
    return out;
}
ll dinic()
{
    ll sum=0;
    while(spfa())
    {
        memcpy(cur,head,sizeof(head));
        while(ll d=dfs(s,inf))
            sum+=d;
    }
    return sum;
}
int main()
{
    ios::sync_with_stdio(false);
    init();

    /* 洛谷输入格式 */
    cin>>n>>m>>s>>t;

    /* LOJ输入格式 */
    // cin>>n>>m; s=1; t=n; 

    int x,y;
    ll w,cost;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>w>>cost;
        add_edge(x,y,w,cost);
    }
    ll maxflow=dinic();
    printf("%lld %lld\n",maxflow,mincost);
    return 0;
}