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