最大流

约 554 个字 77 行代码 预计阅读时间 3 分钟

讲课链接

Dinic时间复杂度

$O(V^2E)$，如果用在二分图，是 $O(E\sqrt V)$

常见技巧

超级源点和超级汇点

多源点或者多汇点，建立超级源和超级汇，把所有的题目中的可行源点和汇点分别连接到超级源和超级汇上

拆点

点权，把一个点拆成入点和出点，即可转化为边权

割点，把一个点拆成入点和出点，即可转化为割边

按照时间拆点，把这些点拆成总时间这么多个点，然后每个点向下一秒的自己连边，如果从A点到B点需要3秒，那么每一秒的A点向3秒后的B点连边，能解决限定时间的最大流问题

加点

同一点集合内任意两点边权一样，不同集合间的点边权不一样，那么每个集合都增加一个点，所有集合内的点向该点连边 参考资料

常见结论

割：把图分为两部分，一个点要么在源点所在的图，要么在汇点所在的图，两个原来有边的点，被分割到两个图后，这个边被割掉

割的容量：割掉的边的边权之和

最小割：容量最小的割=最大流。

闭合图：在一个图中，我们选取一些点构成集合，记为V，且集合中的出边，所指向的终点(弧头)也在V中

闭合图的权：集合中，点权值之和

最大权闭合图：权最大的闭合图=正点权和-最小割。

二分图最大匹配=最大流。

二分图最小点覆盖：选最少的点，满足每条边至少有一个端点被选。

二分图最小点覆盖=最大流。

二分图最大独立集：选最多的点，满足两两之间没有边相连。

二分图最大独立集=点数-最小覆盖数。

二分图最小路径覆盖：有向无环图G，要求用尽量少的不相交的简单路径覆盖所有的节点 。

二分图最小路径覆盖=原图节点数-最大匹配.

板子

const int N=3.2e3;
const int M=1e6+3;
const ll INF=1e18;
namespace Dinic
{
    struct Edge
    {
        int v,nxt;
        ll cap;
    }e[M];
    int n,s,t,tot,hd[N],dep[N],cur[N];
    queue<int> q;
    void init(int nn)
    {
        n=nn,s=nn+1,t=nn+2;
        memset(hd,0,sizeof(int)*(n+3));
        tot=1;
    }
    void addEdge(int x,int y,ll cap)
    {
        e[++tot]={y,hd[x],cap};
        hd[x]=tot;
        e[++tot]={x,hd[y],0};
        hd[y]=tot;
    }
    ll findpath(int u,ll in)
    {
        if(u==t)
            return in;
        ll out=0;
        for(int i=cur[u];i && in;i=e[i].nxt)
        {
            cur[u]=i;
            int v=e[i].v;
            if(!e[i].cap || dep[v]!=dep[u]+1)
                continue;
            ll res=findpath(v,min(in,e[i].cap));
            e[i].cap-=res;
            e[i^1].cap+=res;
            out+=res;
            in-=res;
        }
        if(!out)
            dep[u]=0;
        return out;
    }
    ll dinic()
    {
        ll res=0;
        while(1)
        {
            memset(dep,0,sizeof(int)*(n+3));
            memcpy(cur,hd,sizeof(int)*(n+3));
            dep[s]=1;
            q.push(s);
            while(!q.empty())
            {
                int u=q.front();
                q.pop();
                for(int i=hd[u];i;i=e[i].nxt)
                {
                    int v=e[i].v;
                    if(!e[i].cap || dep[v])
                        continue;
                    dep[v]=dep[u]+1;
                    q.push(v);
                }
            }
            if(!dep[t])
                return res;
            res+=findpath(s,INF);
        }
    }
};
Dinic::init(n);//源点为n+1，汇点为n+2
Dinic::addEdge(u,v,w);//边的顺序一定是源点-中间点-汇点
Dinic::dinic();