最大流
EK 算法
复杂度：(O(nm^2))
所以，关于 (operatorname{EK}) ，他死了
#define Maxn 205
#define Maxm 5005
#define inf 0x7f7f7f7f
int n,m,sum=0,tot=1;
int pre[Maxn],ds[Maxn],hea[Maxn],ver[Maxm],nex[Maxm],edg[Maxm];
bool vis[Maxn];
bool dfs(int s,int t)
{
memset(vis,false,sizeof(vis));
queue<int> q; q.push(s),vis[s]=1,ds[s]=inf;
while(!q.empty())
{
int cur=q.front(); q.pop();
for(int i=hea[cur];i;i=nex[i]) if(edg[i] && !vis[ver[i]])
{
pre[ver[i]]=i,vis[ver[i]]=true;
ds[ver[i]]=min(ds[cur],edg[i]);
if(ver[i]==t) return true;
q.push(ver[i]);
}
}
return false;
}
void EK(int s,int t)
{
while(dfs(s,t))
{
int x=t;
while(x!=s)
{
int i=pre[x];
edg[i]-=ds[t],edg[i^1]+=ds[t];
x=ver[i^1];
}
sum+=ds[t];
}
}
EK(s,t);
dinic 算法
多路增广：
每次增广前，我们先用 BFS 来将图分层,建立残量网络。设源点的层数为 (0) ，那么一个点的层数便是它离源点的最近距离。
当前弧优化：
如果一条边已经被增广过，那么它就没有可能被增广第二次。那么，我们下一次进行增广的时候，就可以不必再走那些已经被增广过的边 。
实现：
在建立残量网络的时候对 (cur[]) 进行初始化，表示这一轮寻找曾增广路的 (tmphead[]) ：
for(int i=1;i<=n;i++) cur[i]=hea[i];
之后再每一次寻找增广路的 (dinic) 函数中进行一下操作：
for(int i=cur[u];i && rest;i=nex[i])
{
cur[u]=i;
...
}
最坏复杂度为 (O(n^2m)) （一般跑不到这个上界） ，而在二分图网络中，复杂度可以达到 (O(sqrt{n}m))
所以，关于 (operatorname{Dinic}) 他快死了 。
模板代码：
#define inf 0x7f7f7f7f
#define Maxn 205
#define Maxm 5005
int n,m,s=201,t=202,tot=1;
int hea[Maxn],tmphea[Maxn],nex[Maxm<<1],ver[Maxm<<1],edg[Maxm<<1];
int dep[Maxn],que[Maxn],ql,qr;
ll sum;
void add(int x,int y,int d)
{
ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
}
bool bfs()
{
memset(dep,0,sizeof(dep)),dep[s]=1;
que[ql=qr=1]=s;
while(ql<=qr)
{
int cur=que[ql++];
for(int i=hea[cur];i;i=nex[i]) if(edg[i] && !dep[ver[i]])
dep[ver[i]]=dep[cur]+1,que[++qr]=ver[i];
}
memcpy(tmphea,hea,sizeof(hea));
return dep[t];
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int rest=flow;
for(int i=tmphea[x],tmp;i && rest;i=nex[i])
{
tmphea[x]=i;
if(edg[i] && dep[ver[i]]==dep[x]+1)
{
if(!(tmp = dinic(ver[i],min(rest,edg[i])))) dep[ver[i]]=0;
edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
}
}
return flow-rest;
}
int flow;
while(bfs()) while(flow=dinic(s,inf)) sum+=1ll*flow;
printf("%lld
",sum);
ISAP
我们发现每一次都进行 ( ext{bfs}) 太慢了，才有了 ISAP。
与 dinic 的一些区别：
-
我们将 dinic 的每一次都进行一次分层，改为进行一遍从 (t) 开始倒序分层，并把原来的层数加一改为层数减一。
-
我们每一次增广完一个点后都将这个点的深度提高，来保证每一条边都都会被访问过。
-
如果访问下一个点时，发现流量等于 (0)，在这里不再将它深度设为 (0)，而是继续访问。
-
如果我们发现此时 (flow)（到这个点时的最大流量）已经用完了，那么直接返回。
-
每次更改点的深度时都记录每一种深度上的点的个数，若某一个深度上已经没有点了，那么可以可以直接结束程序（断层了）。
该优化被称为 GAP 优化。
ISAP 也满足当前弧优化。
最坏复杂度：(O(n^2m))，同 dinic，不过常数、实际运行速度优于 dinic。
还是学学预流推进吧。。
struct ISAP
{
#define Maxn 205
#define Maxm 5005
int _n,tot=1,_s,_t,All;
int dep[Maxn],cnt[Maxn];
int tmphea[Maxn],hea[Maxn],nex[Maxm<<1],ver[Maxm<<1];
ll sum,edg[Maxm<<1];
inline void init(int n,int s,int t)
{
// tot=1; 看情况决定是否要加
All=_n=n,_s=s,_t=t,dep[s]=dep[t]=cnt[n+1]=cnt[n+2]=0;
for(int i=1;i<=n;i++) dep[i]=0,cnt[i]=0;
}
inline void add_edge(int x,int y,ll d)
{
ver[++tot]=y,nex[tot]=hea[x],hea[x]=tot,edg[tot]=d;
ver[++tot]=x,nex[tot]=hea[y],hea[y]=tot,edg[tot]=0;
}
void bfs()
{
queue<int> q; q.push(_t),dep[_t]=1;
while(!q.empty())
{
int cur=q.front(); q.pop();
for(int i=hea[cur];i;i=nex[i]) if(!dep[ver[i]])
dep[ver[i]]=dep[cur]+1,q.push(ver[i]);
}
for(int i=1;i<=_n;i++) cnt[dep[i]]++;
if(_s>_n) cnt[dep[_s]]++,All++;
if(_t>_n) cnt[dep[_t]]++,All++;
}
ll dfs(int x,ll flow)
{
if(x==_t) return flow;
ll used=0;
for(int i=tmphea[x],tmp;i;i=nex[i])
{
tmphea[x]=i;
if(edg[i]>0 && dep[ver[i]]==dep[x]-1)
{
if((tmp = dfs(ver[i],min(flow-used,edg[i]))) > 0)
edg[i]-=tmp,edg[i^1]+=tmp,used+=tmp;
if(used==flow) return flow;
}
}
if(!(--cnt[dep[x]])) dep[_s]=All+1;
cnt[++dep[x]]++; return used;
}
inline ll solve()
{
bfs(),sum=0;
while(dep[_s]<=All) memcpy(tmphea,hea,sizeof(hea)),sum+=dfs(_s,infll);
return sum;
}
#undef Maxn
#undef Maxm
}G;
Push-Relabel 预流推进算法
咕咕咕
HLPP 算法
复杂度：(O(n^2sqrt m))
咕咕咕
费用流
EK
也叫做 (operatorname{MCMF}) 算法
模板代码：
#define Maxn 5005
#define Maxm 50005
#define inf 0x7f7f7f7f
int n,m,sum,hua,tot=1;
int hea[Maxn],ver[Maxm*2],nex[Maxm*2],edg[Maxm*2],Cos[Maxm*2];
int pre[Maxn],ds[Maxn],liu[Maxn];
bool inq[Maxn];
bool spfa(int s,int t)
{
memset(ds,inf,sizeof(ds)),memset(liu,inf,sizeof(liu)),memset(inq,false,sizeof(inq));
queue<int> q; q.push(s),ds[s]=0,inq[s]=true,pre[t]=-1;
while(!q.empty())
{
int cur=q.front(); q.pop(),inq[cur]=false;
for(int i=hea[cur];i;i=nex[i]) if(edg[i]>0 && ds[vis]>ds[cur]+Cos[i] && ds[cur]+Cos[i]>=0)
{
liu[ver[i]]=min(liu[cur],edg[i]);
pre[ver[i]]=i,ds[ver[i]]=ds[cur]+Cos[i];
if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
}
}
return pre[t]!=-1;
}
void EK(int s,int t)
{
while(spfa(s,t))
{
int x=t;
while(x!=s)
{
int i=pre[x];
edg[i]-=liu[t],edg[i^1]+=liu[t];
x=ver[i^1];
}
hua+=ds[t]*liu[t];
sum+=liu[t];
}
}
EK(s,t);
printf("%d %d
",sum,hua);
dinic（类 dinic 算法）
只用将 DFS 改为 (operatorname{SPFA}) 就可以了，将记录深度的 (d) 数组变为 (ds) ，选取增广路的之后判断改为：
if(... && ds[ver[i]]==ds[u]+Cost[i]) ...
注意加上当前弧优化，复杂度为 (O(nmf)) ，其中 (f) 为流量 。
模板代码：
#define Maxn 5005
#define Maxm 50005
#define inf 0x7f7f7f7f
bool spfa()
{
memset(ds,inf,sizeof(ds)),memcpy(tmphea,hea,sizeof(hea));
queue<int> q; q.push(s),ds[s]=0,inq[s]=true;
while(!q.empty())
{
int cur=q.front(); q.pop(),inq[cur]=false;
for(int i=hea[cur];i;i=nex[i]) if(edg[i]>0 && ds[ver[i]]>ds[cur]+Cost[i])
{
ds[ver[i]]=ds[cur]+Cost[i];
if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
}
}
return ds[t]!=inf;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int rest=flow; inq[x]=true;
for(int i=tmphea[x];i && rest;i=nex[i])
{
tmphea[x]=i;
if(!inq[ver[i]] && edg[i]>0 && ds[ver[i]]==ds[x]+Cost[i])
{
int tmp=dinic(ver[i],min(rest,edg[i]));
if(!tmp) ds[ver[i]]=0;
sum_cos+=1ll*Cost[i]*tmp,edg[i]-=tmp,edg[i^1]+=tmp,rest-=tmp;
}
}
inq[x]=false; return flow-rest;
}
int flow;
while(spfa()) while(flow=dinic(s,inf)) sum_liu+=1ll*flow;
最小割
给定一个网络 (G=(V,E)) ，源点和汇点为 (S) 和 (T) ，若删去边集 (E'subseteq E) ，使得 (S) 和 (T) 不连通，则该边集成为网络的割。边的容量值和最小的割成为该网络的最小割。
( ext{最小割} = ext{最大流})