Day3上午——图论
一、强联通分量
强联通分量即是环
极大强联通子图：将原图中任何点加入这个子图都不能构成强联通分量的强联通分量。
极大不一定最大。
强联通分量针对有向图。
途中每个点都属于且仅属于一个极大强联通分量。
强联通分量与点的关系具有传递性。
求强联通分量可以使用Tarjan算法或者Kosaraju算法，我们主要使用Tarjan算法。
二、Tarjan算法
考虑当前dfs到某个点now,其余点只有三种：
①可以访问到的点
②不能访问到的点
③未访问的点
dfs的过程中，如果从某一点出发可以回到这个点，那么一定会存在一个强联通分量，而这个强联通分量就在dfs的栈里，所以我们可以用一个栈记录一下经过的点，去找强联通分量。
定义dfn[x]为搜索到x的时间，即编号，low[x]为从x出发可以走到的最小点。我们发现如果从某点出发搜完之后low[x]==dfn[x]，说明此时从x出发有一个强联通分量，此时我们把记录的栈弹出至遇到x就是一个强联通分量。
缩点
缩点后，新图为一个DAG。
例题一、The Cow Prom
题面见P2863。
tarjan裸题。
例题二、受欢迎的牛
题面见P2341。
思路
首先缩点，发现如果某个点只有入度且只有这个点是只有入度的，那么这个点就是要求的点，否则不存在。
例题三、稳定婚姻
题面见P1407。
思路
夫妻男连女，情人女连男，跑一边tarjan，如果一对夫妻在同一个强联通分量中，这段婚姻就是不稳定的。
三、双联通分量
割点和桥
将点$x$删掉后，图中联通分量个数增加，称$x$为割点。
将边$e$删掉后，图中联通分量个数增加，称$e$为桥。
点双联通分量：两点间的所有路径不经过同一点的联通分量。
边双联通分量：两点间的所有路径不经过同一边的联通分量。
割点求法
类似于tarjan，如果x有一个出点low值$\ge dfn[x]$说明x是割点，注意要特殊处理第一个搜索的点。
边双联通分量求法
和求强联通分量几乎一样，判断一下不走回头路就行了，不能走走过的边。
扔个模板1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44...
int nt[N], b[N], p[N], num = 1, st[N], dfn[N], low[N], ltk[N], id;
bool flag[N];
inl void add(rg int x, rg int y)
{
b[++num] = y, nt[num] = p[x], p[x] = num;
b[++num] = x, nt[num] = p[y], p[y] = num;
}
void tarjan(rg int x)
{
dfn[x] = low[x] = ++id;
st[++*st] = x;
for (rg int e = p[x]; e; e = nt[e])
if (!flag[e])
{
rg int k = b[e];
if (!dfn[k])
{
flag[e] = flag[e ^ 1] = true;
tarjan(k);
flag[e] = flag[e ^ 1] = false;
low[x] = fast_IO::min(low[x], low[k]);
}
else low[x] = fast_IO::min(low[x], dfn[k]);
}
if (dfn[x] == low[x])
{
++*ltk;
while (st[*st + 1] != x)
{
ltk[st[*st]] = *ltk;
--*st;
}
}
}
int main(void)
{
...
for (rg int i = 1; i <= m; ++i)add(fast_IO::read(), fast_IO::read());
for (rg int i = 1; i <= n; ++i)if (!dfn[i])*ltk = 0, tarjan(i);
...
return 0;
}
例题一、冗余路径Redundant Paths
题面见P2860。
思路
先求边双联通分量，缩点后成了一颗树，这棵树的度数为1的点的数量sum，答案就是⌈$sum/2$⌉，答案的正确性显然，因为每个度数为1的节点肯定需要连边出去，贪心的想就很容易证明了。
点双联通分量求法
在求割点的过程中就能求出，稍微改动一下就行，我们考虑将经过的边入栈而不是经过的点，在找到割点的时候，把边一个个从栈中取出直到遇到边$(u,v)$，取出的边与其关联的点构成一个点双联通分量。
由于点双联通分量求法不太一样，扔个模板吧。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56struct Node {
int u, v;
}e[N], st[N], tp;
int nt[N], p[N], top, dfn[N], low[N], id, gedian[N], bcc_cnt, belong[N];
vector<int>bcc[N];
void tarjan(rg int x, rg int fa)
{
rg int child = 0;
dfn[x] = low[x] = ++id;
for (rg int k = p[x]; k; k = nt[k])
{
rg int to = e[k].v;
st[++top] = e[k];
if (!dfn[to])
{
++child;
tarjan(to, x);
low[x] = fast_IO::min(low[x], low[to]);
if (low[to] >= dfn[x])
{
gedian[x] = true;
bcc[++bcc_cnt].clear();
do {
tp = st[top--];
if (belong[tp.u] != bcc_cnt)
{
bcc[bcc_cnt].push_back(tp.u);
belong[tp.u] = bcc_cnt;
}
if (belong[tp.v] != bcc_cnt)
{
bcc[bcc_cnt].push_back(tp.v);
belong[tp.v] = bcc_cnt;
}
} while (tp.u != e[k].u || tp.v != e[k].v);
}
else if (e[k].v != fa)low[x] = fast_IO::min(low[x], dfn[to]);
}
}
if (!fa)
{
if (child > 1)gedian[x] = true;
else gedian[x] = false;
}
}
...
int main()
{
...
for (rg int i = 1; i <= n; ++i)
if (!dfn[i])tarjan(i, 0);
...
return 0;
}
四、二分图
二分图的判定
对二分图黑白染色，如果产生矛盾说明不是二分图。（二分图中无奇环）。
Hall定理
设二分图中$G=
匈牙利算法
贪心，过程比较简单，扔个模板1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28vector<int>e[N];
int mat[N];
bool flag[N];
bool dfs(rg int x)
{
for (rg int i = 0; i != e[x].size(); ++i)
{
rg int j = e[x][i];
if (flag[j])continue;
flag[j] = false;
if (!mat[j] || dfs(mat[j]))return mat[j] = x;
}
return false;
}
...
int main()
{
...
for (rg int i = 1; i <= n; ++i)
{
if (dfs(i))++ans;
memset(flag, 0, sizeof(flag));
}
...
return 0;
}
几个定理
二分图最小点覆盖==二分图最大匹配
点覆盖：在图中选取一些点，保证每条边至少有一个点在选取点中，称这些点是一个点覆盖。
二分图最大点独立集==总点数-二分图最大匹配
独立集：在图中选取一些点，保证每个点不相邻，则称这些点是一个独立集。
例题一、Asteroids 小行星
题面见POJ3041。
思路
行列分开，对于小行星的坐标$(x,y)$，连边$(x,y)$，跑二分图匹配求最小点覆盖即是答案。
例题二、Muddy Fields 泥泞的牧场
题面见POJ2226
思路
和前面那道例题类似，贪心的考虑，每块板子肯定是延伸到最长最好，所以我们把一些板子分成两部分：$A$部分是所有横着的木板，$B$为所有竖着的木板，将横竖交叉的木板连边，构成一个二分图，这样选择一个点就代表选择一个板子，求最小点覆盖就是我们要求的答案。
五、2-SAT
SAT问题是给出一些条件（元素经过逻辑运算的结果，如and or xor），SAT问题已经被证明是一个NP完全问题。
2-SAT问题中最多有两个条件。
求法
对于每个变量$x$，建立两个点$x_t$和$x_f$，分别表示$x$取TRUE和$x$取FALSE。对于所有的“A取x则B取y”，连边$(A_x,B_y)$，该图中如果P能到达Q，表示“若P成立，则Q一定成立”
所以如果从$a_f$出发能到达$a_t$或者$a_t$出发能到达$a_f$，则矛盾。
这一步的检验我们考虑用tarjan求联通分量，$O(N)$解决。
如果没有这种情况出现，则一定存在合法方案。
现在我们考虑如何构造一组可行解
我们构造这样一种方案：缩点之后按照“逆拓扑序”挑选一个未被染色的强联通分量将其染成黑色，然后把所有与这个强联通分量里的点矛盾的点所在的联通分量染成白色。最后所有染成黑色的强联通分量里的点就是选择的方案。
例题一、NOI2017 游戏
题面见P3825
思路
对于$a,b,c$，就直接裸的2-SAT。
对于$x$，如果直接枚举选$A,B,C$中的哪个，复杂度要乘上$3^d$，但是如果我们考虑枚举x不适合哪辆车，复杂度就乘上$2^d$。
Day3下午
一、网络流
除了源点和汇点，所有点的输入与输出平衡。
求法
Ford-Fulkerson算法
Dinic
SAP
等等。。。
个人觉得用dinic就够了……
二、Dinic
反向边：用于反悔，保证所有操作可撤销。
优化
当前弧优化
三、最小割
最小割定理
最小割==最大流
例题一、吃饭Dining
题面见P2891。
思路
把牛拆成两个点，这两个点之间连容量为1的边，原点连食物，食物连牛，牛连饮料，饮料连汇点，跑最大流。
经典最小割模型——最大闭合子图
图中的点有点权，点权可正可负，在图中选一些点，如果有边$(u,v)$则选u必选v。
解法
建图：对于权值为正$x$的点，从源点连一条容量为$x$的边，权值为负$y$的点，向汇点连一条容量为$y$的边，原图边容量为正无穷（较大值）。
例题二、NOI2006 最大获利
题面见P4174。
思路
将题目中的边都看成点
边对应的点依赖于原图中的点
将边转化为点，则该图转化为一个二分图
求这个二分图的最大闭合子图就行了。
经典最小割模型——二分图最小点权覆盖
给出一个二分图，每个点有非负点权
选出一些点构成一个覆盖，求最小点权和
解法
源点向左边的点连容量为点权的边，右边的点向汇点连容量为点权的边，求最小割即可。
例题三、游戏
一张图，删除每个点的入边有费用$w_i+$，删除每个点的出边有费用$w_i-$，求删除所有边需要的最小费用。
思路
将所有入边和出边看成点，同一条边之间连容量无穷大的边，构成一个二分图，求这个二分图的最小点权覆盖就行了。
经典最小割模型——二分图最大点权覆盖
给出一个二分图，每个点有非负点权
选出一些点构成一个覆盖，求最大点权和
解法
点权和减去最大流。
例题四、方格取数问题
题面见P2774
思路
黑白染色成一个二分图，跑最小割，用全局和-最小割即可。
四、费用流
图中的边不仅有容量，还有费用。
最小费用最大流：流量最大的情况下费用最小
最小费用流：跑最短路，如果途中发现跑某条路径会使费用变大，就停止，最大费用流同理。
例题一、晨跑
题面见P2153
思路
拆点限流，连边直接跑费用流出解。
经典费用流模型——连续$M$个元素最多选$K$个
给定$n$个元素，每个元素有权值$a_i$（可正可负），要求从中选出一些，满足其中任意相邻$M$个元素中只有最多$K$个元素被选出。
解法
把题目转换为选$K$次，每次要求选出的点距离大于$M$，建图的时候从每个点$i$向$i+M$连边，容量为1，费用为$a_i$，相邻点之间连边，费用为0容量为$INF$，源点向第一个点连边，容量为$K$费用为0，最后一个点向汇点连边，容量为$INF$费用为0，跑费用流即可。
例题二、数字配对
题面见P4068。
思路
设$cnt_i$表示第i个数字质因数分解后各质因数的指数和。
按照cnt的奇偶性，将这些数字分为两个集合。
从源点向所有$cnt_i$为奇数的点连容量为$b_i$，费用为0的边。
从所有$cnt_i$为偶数的点向汇点连容量为$b_i$，费用为0的边。
对于一对$a_i$和$a_j$，如果$a_i$和$a_j$能匹配且$cnt_i$为奇数，连边，容量为$INF$，费用为$c_i\times c_j$。
考虑贪心，跑最大费用最大流，每次跑最长路，在价值总和不小于0的情况下尽量增加流量，如果找不到增广路或者增广下去会使费用小于0则说明找到了答案。
例题三、方格取数问题
题面见P2045。
思路
拆点，两点之间连两条边，第一条边费用是该点权值，流量是1，另一条边费用是0，流量是$INF$。从源点向左上角连费用为0，流量为$K$的边，右下角向汇点连边，费用为0，流量为$INF$，跑最大费用最大流。
例题四、修车
题面见P2053。
思路
一个工人拆成$n$个点，表示n个时间段的工人，将$n$辆车与这$m \times n$个点都连起来，容量为1，费用为工人的时间段$\times$输入的时间，源点到车费用为0，流量为1，工人到汇点费用为0，流量为1，跑最小费用最大流即可，最后答案用总时间除以车数。
例题五、费用流
题面见P3305。
思路
二分最大的容量，跑dinic。
例题六、小M的作物
题面见P1361。
思路
按题目建图，一个点拆成两个点
五、上下界网络流
每条边除了流量上界，还有流量下界。
解法
这里借用了这篇博客 感觉总结的非常好
①无源汇有上下界可行流（循环流）
模型:一个网络,求出一个流,使得每条边的流量必须$\ge L_i$且$\le H_i$,每个点必须满足总流入量$=$总流出量(流量守恒)(这个流的特点是循环往复,无始无终)。
可行流算法的核心是将一个不满足流量守恒的初始流调整成满足流量守恒（所有点的流入量$=$流出量）的流。
我们可以令每条边的流量为该边的下界得到一个初始流，然后建出这个流的残量网络（每条边的上界与下界之差）。
考虑在残量网络上求出一个附加流，使得附加流与可行流合并之后达到流量守恒，即：
1)如果某个点在所有边流量等于下界的初始流中满足流量守恒,那么这个点在附加流中也满足流量守恒,
2)如果某个点在初始流中的流入量比流出量多$x$,那么这个点在附加流中的流出量比流入量多$x$.
3)如果某个点在初始流中的流入量比流出量少$x$,那么这个点在附加流中的流出量比流入量少$x$.
$x$可以通过枚举点$i$的所有连边求出，开一个数组$A[]$，统计$i$点的流入量-流出量大小，根据$A_i$的正负表示流入量与流出量的大小关系。
我们在残量网络中加入一些点和边，首先是虚拟超级源$ss$和虚拟超级汇$tt$。如果$A_i<0$，从$i$向$tt$连一条容量为$-A_i$的边，反之从$ss$向$i$连一条容量为$A_i$的边。
最后在建出的图上跑最大流，如果$ss$和$tt$连接的边都是满流的说明存在可行流，每条边在可行流中的流量$=$容量下界$+$附加流中它的流量（即反向边的权值）。
②有源汇有上下界可行流
模型:现在的网络有一个源点$s$和汇点$t$,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制。
从$t$向$s$连一条下界为0，上界为$INF$的边，改成无源汇上下界可行流，跑完之后拆掉这条边就得到有源汇上下界可行流。
最终的流量为这条边的反向边流量。
③有源汇有上下界最大流
模型:现在的网络有一个源点$s$和汇点$t$,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制。在这些前提下要求总流量最大。
先跑出可行流，再在残量网络上跑出$s-t$最大流，最终的最大流$=$可行流流量$+$新增广出的$s-t$流量。
④有源汇有上下界最小流
模型:现在的网络有一个源点$s$和汇点$t$,求出一个流使得源点的总流出量等于汇点的总流入量,其他的点满足流量守恒,而且每条边的流量满足上界和下界限制。在这些前提下要求总流量最小。
还是先跑出可行流，然后再残量网络上跑出$t-s$最大流，最终的最小流$=$可行流-$t-s$的最大流。