跳转至

最大流

约 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();