__builtin_popcount原理

小学期题用了这个函数觉得十分高级学习一个

这个函数用来数二进制数中1的个数正常的操作是unsigned int二进制表示下最右端是不是1若是1则计数器+1再右移重复32次这样的操作需要进行32次int运算效率不够高这个问题可以二分解决

Read More

CF630D2F

将每个独立集$V$考虑为原图中被染色的一些顶点而在原图中加边后$E'$可以得到一个子图$G'$这个子图如果满足一些条件$V$就是$E'$生成的子图$G'$中的一个独立集这些条件为

  1. 一条边的两端不同时被染色$V$中任意两点间没有边
  2. 没有孤立顶点被染色$V$中的每个点都应当与$E'$中的一条边相连

Read More

CF620D2E

由于一条路径可以包含一条边多次所以如果$a$能经历$k$条边到达$b$那就可以经过$k+2n$条边到达$b$只需要在路径中随便找一条边不停折返即可于是考虑对树黑白染色注意结论树是二分图从而可以dfs染成黑白两色方便考虑

Read More

Dinic算法

本文讲解Dinic算法的思路算法本身与证明

关于残余网络增广路等概念的说明请看Ford-Fulkerson算法这篇文章这里只致力于改进Ford-Fulkerson算法得到一个与$F$无关的算法

问题

$F$较大时影响Ford-Folkerson算法效率的主要因素在于每次dfs可能可以找到许多条路径但是该算法中每次dfs只进行一次增广这就导致增广次数与$F$可能相关一种想法是一次dfs多次增广但这样做能否成功是取决于dfs顺序的于是考虑dfs顺序如何时效率较高呢

思路

Dinic算法的核心是每次寻找最短的增广路并进行增广这样做的理由既是依据也是好处每次沿最短增广路增广后最短增广路的长度一定不会减少稍后会给出证明假如有了这一结论每次找到最短增广路的长度时将该长度的增广路[全部增广]然后重新寻找最短增广路其长度至少增1而增广路长度不会超过$|V|$因为增广路是简单路径从而增广次数上界$O(|V|)$

证明

下面证明每次沿最短增广路增广后最短增广路的长度一定不会减少在原图上为寻找最短增广路$s$出发bfs设第一次到达点$v$的边为$\langle u,v\rangle$为点$v$编号$n_v=n_u+1$由bfs的特性每条边增量指该边终点与起点编号差可为负值后均同不超过1特别地$n_s=0,s$为源点称这个图为分层图

此时有结论$n_t$被更新那么最短增广路的长度为$n_t$为了证明可以寻找为$n_t$标号的边的出发点$i$再寻找为$i$标号的边的出发点$j$最终会回到$s$并且沿每条边标号增1由于每条边增量不超过1每条边都增1是从0到$n_t$最快的方法从而我们找到了一条最短增广路$l_{min}$并且每个最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$

下面使用数学归纳法

1分层图上沿最短增广路增广1次后新图中可能出现一些新的反向边若新图中有增广路$l'$其中的边的来源有两种可能

1边原分层图中的边bfs时经历过的边$\langle u,v\rangle$满足$n_v\leq n_u+1$

2边增广时出现的反向边$\langle v,u\rangle$记原边为$\langle u,v\rangle$那么由于原边在最短增广路中一定满足$n_v=n_u+1$

那么沿该路径中任何一条边编号增加不超过1为了从$0$到达$n_t$仍然至少需要$n_t$条边长度没有变短所以最短增广路长度没有减少并且所有边都仍满足$n_v\leq n_u+1$

2假设沿最短增广路增广n次后最短增广路长度不减少当增广$(n+1)$次后若图中无增广路结论成立若图中仍有增广路其中的边可能是

1边增广n次后的图中的边$\langle u,v\rangle$满足$n_v\leq n_u+1$

2边$(n+1)$次增广时出现的反向边$\langle v,u\rangle$记原边为$\langle u,v\rangle$那么由于原边在最短增广路中一定满足$n_v=n_u+1$

类似于上面可以证明沿最短增广路增广$(n+1)$次后最短增广路长度仍不减少并且所有边都仍满足$n_v\leq n_u+1$

综上沿最短增广路增广后最短增广路长度不会减少

优化

首先在证明中我们知道最短增广路中的每条边$\langle u,v\rangle$都满足$n_v=n_u+1$从而我们只考虑递增的边不会出现错误实际上每次分层完后只要找到增广路就可以增广不必局限在最短增广路中增广这是自缚手脚只考虑递增的边的情况下 情况立刻不同了图成为了DAG从而$\langle u,v\rangle$能否使用只与$v$可达的点记符合条件的点集为$V$那么$\forall g \in V$$n_g>n_v$的情况有关而与$s$如何到达$u$无关从而如果某一时刻发现一条边不能使用那么在重新bfs即重新标号之前无论其他地方如何增广其后的边流量只会减少不会增加这条边都仍然不能用来增广于是可以记录这些边使之只遍历一次每次分层至多访问它们$O(|E|)$

算法描述

下面的算法只是大致的描述没有伪代码那么明确重在讲清楚过程希望我做到了

Dinic算法输入网络$G(V,E)$ 输出最大流$max\_flow$

步骤0. [准备]建立数组$iter[V]$定义$max\_flow\gets0$用邻接表$G[V]$存储网络

步骤1. [建立分层图]bfs(s,0)当bfs(u,n)时$n_u$已定义返回否则记$n_u=n$并对$G[u]$中的所有元素$v$进行bfs(v, n+1)清零$iter[]$数组

步骤2. [有增广路吗]若$n_t$未定义退出算法返回$max\_flow$

步骤3. [寻找增广路]在$G$上DFS寻找从$s$$t$的简单路径要求该路径上每条边$e\langle u,v\rangle$可用权值$(w_e-f_e)$大于0并且$n_v>n_u$若找到记该路径上的权值最小的边权值为$f$否则$f\gets0$DFS(u)时按顺序遍历$G[u]$$G[u][i]$不可用$iter[u]\gets iter[u]+1$

步骤4. [找到了更新残余网络]如果$f>0$$max\_flow\gets max\_flow+f$对路径上的每条边$e$$f_e\gets f_e+f$记其反向边为$e'$$w_{e'}\gets w_{e'}+f$返回步骤3

步骤5. [没有找到]如果$f=0$返回步骤1

复杂度

由于每次dfs都至少使一条边满流从而使之无法使用dfs次数上界为$O(|E|)$在当前弧优化后每次dfs经过的边有两种可能性1是无用边2在增广路里其中1无用边在一次分层内总共访问$O(|E|)$2成功增广的情况中增广路长度不超过$|V|$每次分层中情况2的总复杂度上界为$O(|E||V|)$从而每次分层的复杂度上界为$O(|E||V|+|E|)=O(|E||V|)$从而Dinic算法总的时间复杂度为$O(|E||V|^2)$

模板

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge{
    ll to, w, rev;
};
vector<edge> G[V];
int num[V], iter[V];
int s, t;//源点和汇点<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>是全局变量

ll max_flow();
ll dfs(ll u, ll f);
void bfs();
void add_edge(ll from, ll to, ll w);

ll max_flow() {
    ll f = 0, flow = 0;
    while(true) {
        memset(iter, 0, sizeof(iter));
        bfs();
        if(num[t] == -1) return flow;
        while(f = dfs(s, INF)) {
            flow += f;
        }
    }
}
ll dfs(ll u, ll f) {
    if(u == t) return f;
    ll flow;
    for(int &i = iter[u]; i < G[u].size(); i++) {
        edge &e = G[u][i];//注意是引用<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>需要直接修改原图
        if(e.w > 0 && num[u] < num[e.to]) {
            if(flow = dfs(e.to, (f > e.w ? e.w : f))) {
                //min函数有些编译器不给过<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>所以用三目
                e.w -= flow;
                //直接修改容量而非同时记录f和w<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>只是为了方便
                G[e.to][e.rev].w += flow;
                return flow;
            }
        }
    }
    return 0;
}
void bfs() {
    memset(num, -1, sizeof(num));
    queue<int> que;
    que.push(s);
    num[s] = 0;
    while(!que.empty()) {
        int u = que.front(); que.pop();
        for(int i = 0; i < G[u].size(); i++){
            edge &e = G[u][i];
            if(e.w > 0 && num[e.to] < 0) {
                num[e.to] = num[u] + 1;
                que.push(e.to);
            }
        }
    }
}
void add_edge(ll from, ll to, ll w) {
    G[from].push_back(edge{to, w, G[to].size()});
    G[to].push_back(edge{from, 0, G[from].size() - 1});
}

如有发现模板的错误请联系我指正我将不胜感激

网络流

最大流问题

举个例子互联网上有几台计算机某些计算机之间建立了一定带宽的有向连接目标是将数据从某台指定的计算机$s$称为源点传输到$t$称为汇点求单位时间内最多能传输多少数据

有许多类似的问题都可以抽象成类似的网络流问题上面的问题是一个单源单汇最大流问题形式化地描述即为

对无重边与自环的有向图$G(V,E)$若每条边$e\in E$有一个权值$w_e$称作该边的容量$s\in V,t\in V$称该图为一个网络若一个有向图$G'(V,E)$满足$G'$$G$完全相同除去每条边$e\in E$有另一个权值$f_e$称作该边的流量以外并且对$\forall u\in V,u\ne s,u\ne t$满足$\sum\limits_{e=\langle u,v\rangle}{f_e}=\sum\limits_{e=\langle v,u\rangle}{f_e}$即流入每个顶点的流量等于流出的流量那么称该有向图$G'$为网络$G$上的一个流该流的流量$f$定义为$\sum\limits_{e=\langle s,u\rangle}{f_e}$一个网络的最大流是指该网络的所有流中流量最大的那个

通常在不引起歧义的情况下并不区分最大流最大流的流量

对上面的抽象模型解决最大流问题的算法有两类增广路算法和预流推进算法最常用的是增广路算法中的 Ford-Fulkerson 算法和​ Dinic​ 算法这里将常见的算法罗列如下

算法名 算法分类 复杂度
Ford-Fulkerson算法 增广路 $O(FE)$
Dinic算法 增广路 $O(n^2m)$
HLPP我也不会 预流推进 $O(n^2\sqrt{m})$

Ford-Fulkerson算法

本文讲解Ford-Fulkerson算法的思路算法本身与证明最后会给出模板Ford-Fulkerson算法是增广路算法的一种用于求解最大流问题不明背景请看网络流这篇文章

分析

朴素算法

朴素的想法的一种是这样的在图中DFS一旦找到一条从s指向t并且可以在这条路径上添加流量每条边$e$都满足$f_e<w_e$那么就在这条路径的所有边上同时不断添加流量直到无法再添加某条边$e$$f_e=w_e$直到无法再找到任何这样的路径即得到最大流如下图

朴素想法求最大流

上面的图中黑色为边的容量红色为边的容量图1为原来的网络其中1为源点6为汇点图二为DFS时可能得到的一个图可以看到上面的算法在这里就会停止而图三是该网络的最大流可以轻松地验证这一点因为从1出发的边都已经满流了无法再增加新的流量注意DFS可能得到最优解但不是一定得到最优解

所以上述的算法是错误的但是它错在哪里呢

改进

观察图3这个流比图2多的流如图4

朴素想法与最大流之差

从图4看它是把图2中$2\rightarrow4$已有的流量1推了回去而产生的这也正是增广路算法的核心所在但是这看起来不可理喻原图中没有的边为什么凭空造出来一条就正确呢

解释

仔细观察图2和图3就会发现$4\rightarrow6$的边流量没变仍然是1但是$2\rightarrow4$的流量没有了那最大流中谁为4提供那一个流量呢显然是$1\rightarrow3\rightarrow4$的路径同理$1\rightarrow2$的流量也没有变它从$2\rightarrow5\rightarrow6$的路径流出去了这就可以想象成节点4不知道是谁给他的流量也就是在这个过程中4的上游的信息被屏蔽了同时2的下游的信息也被屏蔽了只要有人能为4提供流量他就什么都不知道同样的只要有人能从2运走流量他也什么都不知道这样在新的流中原本只有一份的流量$1\rightarrow3\rightarrow 4$流走了一份$1\rightarrow2\rightarrow5$又流走了一份所以流量+1

所以$\langle u,v\rangle$的反向边$\langle v,u\rangle$的意义就是$\langle u,v\rangle$有流$f$的时候如果有一个路径可以从$v$流入称其前面的那段路经为上游再从$u$流出称其后的那段路径为下游且流为$f_0\le f$那么就可以认为上游为$v$提供原来的一部分流$f_0$而从$u$流入的那些$f_0$改道从下游流出了

上面的做法可以算作对朴素DFS做法的一个修正大概可以理解为避免了因DFS顺序不确定而导致的错误

于是对一个流可以对图上所有有流$f$的边$\langle u,v\rangle$建立反向边$\langle v,u\rangle$其容量为$f$这样得到的新的图称为残余网络残余网络上从$s$$t$的路径叫做增广路残余网络上进行dfs沿着增广路来添加流这就是Ford-Fulkerson算法

算法描述

对网络上的每个流$G(V,E)$定义与之对应的残余网络$G'(V,E')$$f_e>0(e=\langle u,v\rangle\in E)$那么$e\in E'$$rev(e)=\langle v,u\rangle\in E'$并且$w_{rev(e)}=f_e,f_{rev(e)}=0$$E'$中的元素只有刚才描述的那些那么算法可以描述为

Ford-Fulkerson算法

输入网络$G$一个图$G(V,E)$$E$中的边$e$有权重$w_e\in\mathbb{N_+}$$max\_flow=0$

输出该网络上的最大流的流量$f$

步骤0. [建立反向边]定义$max\_flow\gets0$用邻接表G[V]存储网络$E$中的每条边$e=\langle u,v\rangle$作其反向边$e'=\langle v,u\rangle$并置$w_{e'}\gets0$

步骤1. [寻找增广路]在$G$上DFS寻找从$s$$t$的简单路径要求该路径上每条边可用权值$(w_e-f_e)$大于0若找到记该路径上的权值最小的边权值为$f$否则$f\gets0$

步骤2. [找到了更新残余网络]如果$f>0$$max\_flow\gets max\_flow+f$对路径上的每条边$e$$f_e\gets f_e+f$记其反向边为$e'$$w_{e'}\gets w_{e'}+f$返回1

步骤3. [没有找到]如果$f=0$输出$max\_flow$算法结束

最大流不会超过从$s$出发的所有边的边权和而该算法中每次进入步骤1后$f$总是正整数也有$f=0$的情况此时算法结束所以该算法对整数总是有限的若记最大流流量上界为$F$则该算法最多进入步骤1$(F+1)$而每次进入步骤1需要$O(|E|)$的复杂度进行搜索所以总的时间复杂度是$O(F|E|)$但这个复杂度上界是很松的实际用起来效率比较高所以有时即使估计复杂度偏高也可以使用$F$较小的情况则可以轻松应对

证明

在Ford-Fulkerson算法结束后的残余网络上没有$s\rightarrow t$路径所以残余网络上$s$可达的所有点构成的集合$S$不包含$t$$T=V-S$那么$T$不空并且$T\cap S=\varnothing$

结论1$S$指向$T$满足$u\in S,v\in T$的边$e=\langle u, v\rangle$都应当满流$w_e=f_e$否则由于从$s$可达$u$$s$也可以从$s\rightarrow u\rightarrow v$到达$v$那么$v\in S$矛盾

结论2$T$指向$S$满足$u\in T,v\in S$的边$e=\langle u,v\rangle$流量必为0否则$s$可由其反向边到达$u$流入$S$的流量为0反向边就是在这里用到的

对于任意一个流$S-\{s\}$中的点流入的流量都等于流出的流量那么流入$S-\{s\}$的流量$f_{in}$等于从$S$流向$T$的所有边的流量和$S_f$这个和不超过从$S$流向$T$的所有边的容量和$S_w$写在一起就是$f_{in}=S_f\le S_w$从而从$s$流出的流量$f_s$一定不超过$S_w$因为$f_s$应当是$f_{in}$的一部分$f_{s}\le S_w$这是对任意流的结论

而对于残余网络注意残余网络也是一个流由结论1$S_f=S_w$又由结论2$f_s$即为$f_{in}$的全部所以有$f_s=f_{in}=S_w$所以$f_s$为所有流中的最大者

也可以用反证法若存在比Ford-Fulkerson算法得到的流更大的流仍然观察上面的点集$S$此时从$s$流出的流量$f_{s'}$应当超过了$f_x=S_w$这时$S-\{s\}$中的点不可能满足流入每个顶点的流量等于流出的流量所以这样的流不存在

至此就证明了Ford-Fulkerson算法的正确性

模板

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>

#define V 5005 //V为顶点最大个数<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>视数据范围而定
#define INF 0x7fffffffffffffff

using namespace std;
typedef long long ll;
struct edge {
    ll to, w, rev;
};
vector<edge> G[V];
int s, t;//源点和汇点<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>是全局变量
bool vis[V];

ll max_flow();
ll dfs(ll u, ll f);
void add_edge(ll from, ll to, ll w);

ll dfs(ll u, ll f) {
    if(vis[u]) return 0;
    vis[u] = true;
    if(u == t) return f;
    for(int i = 0; i < G[u].size(); i++) {
        edge &e = G[u][i];//注意是引用<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>需要直接修改原图
        if(!vis[e.to] && e.w > 0) {
            ll curf = dfs(e.to, (f > e.w) ? e.w : f);
            //min函数有些编译器不给过
            if(curf > 0) {
                e.w -= curf;
                //直接修改容量而非同时记录f和w<span class="bd-box"><h-char class="bd bd-beg"><h-inner>,</h-inner></h-char></span>只是为了方便
                G[e.to][e.rev].w += curf;
                return curf;
            }
        }
    }
    return 0;
}
ll max_flow() {
    ll maxf = 0;
    while(true) {
        memset(vis, 0, sizeof(vis));
        ll f = dfs(s, INF);
        if(f == 0) break;
        maxf += f;
    }
    return maxf;
}
void add_edge(ll from, ll to, ll w) {
    G[from].push_back(edge(to, G[to].size(), w));
    G[to].push_back(edge(from, G[from].size() - 1, 0));
}

如有发现模板的错误请联系我指正我将不胜感激