图论

并查集

这个没什么好讲的，带权和扩展域相信大家都会，这里就给一道有意思的题吧 link

这个题并查集显然不能直接做，因为修改一个节点也会影响它的儿子，我们要想办法对他儿子的影响给去掉。

于是我们可以借鉴扩展域并查集的思想，新开一倍的节点，用 i+n 来代表合并并查集时用的节点，这样我们修改 i 时，不会影响 i+n 的父亲，达到了单点修改的目的。

二分图

二分图最大匹配

貌似大家只会敲dinic的样子，我给大家讲讲匈牙利算法解决二分图匹配吧，虽然整体时间复杂度不如dinic，但在使用增量法时匈牙利算法有时间复杂度保证而dinic不太行。

算法流程 :

1. 我们从一个未匹配的左部点开始搜索，寻找与之相连的右部点。

2. 如果找到一个未匹配的右部点，则与之匹配，匹配数+1，结束此次增广。

3. 如果找到一个已匹配的右部点，我们可以去搜索 与这个右部点匹配的左部点2 ，让 左部点2 换一个右部点去匹配，这样就能将这个右部点让出来，匹配数+1，结束此次增广。

4. 如果无 2,3 情况，则这个点匹配失败， 结束此次增广。

正确性证明 :

1. 可以看出匈牙利算法基于一个贪心思想：尽量匹配当前的左部点。 因为每个左部点对最大匹配的贡献都是 $1$，所以一个右部点与哪个左部点匹配都是等价的，贪心思想正确。

2. 在寻找匹配点时，如果匹配成功，我们 dfs 的路径将会是一条非匹配边与匹配边交错出现的路径，我们实行的操作就相当于将这条路径取反，因为这条路径上非匹配边比匹配边多一条，所以取反后可以使匹配数增加 $1$，这个路径被称为增广路。

3. 可以证明找不到增广路后无法继续增大匹配数，所以算法正确。

代码实现如下 :

int vis[N], match[N];
bool find(int x, int tag)
{
    if(vis[x] == tag) return false;
    vis[x] = tag;
    for(int i = head[x]; i; i = e[i].next)
    {
        int y = e[i].to;
        if(!match[y] or find(match[y], tag))
        {
            match[y] = x;
            return true;
        }
    }
    return false;
    
}

int main()
{
    int ans = 0;
    for(int i = 1; i <= n; i++)
        ans += find(i, i);
}

一道小例题: P2825 [HEOI2016]游戏

一道很套路的题，经典一行一列只能放一个，只不过这道题的行列定义有一些差别罢了，我们可以把每一行/列被硬石头分成的几个部分看成"小行/列"，跑二分图匹配即可。

二分图最小点覆盖

使用最少的点覆盖二分图的所有边。

König 定理 : 二分图最小点覆盖=二分图最大匹配。

我们尝试构造一个点覆盖 :

1. 先求解二分图最大匹配。
2. 从每个未匹配的左部点出发，执行一次寻找增广路(一定会失败)，并标记经过的节点。
3. 取所有左部未被标记的点和右部被标记的点，就得到了二分图最小点覆盖。

证明所取点数等于最大匹配数 :

1. 左部非匹配点一定被标记(出发点)。
2. 右部非匹配点一定不被标记(否则有增广路)。
3. 一对匹配点一定同时被标记或同时不被标记(走过的匹配边会给这两个点都打上标记)。
4. 根据我们的取法，恰好是每一个匹配边都取了其中一个点。

证明这些点覆盖了所有边 :

1. 匹配边一定被覆盖——取了其中一个点。
2. 不存在连接两个非匹配点的边——否则就找到了增广路。
3. 连接左部非匹配点 $i$， 右部匹配点 $j$ 的边——$i$ 是出发点所以 $j$ 一定被打上标记，我们取了右部所有被标记的点，此类边被覆盖。
4. 连接左部匹配点 $i$，右部非匹配点 $j$ 的边—— $i$ 一定没有被访问，否则再走到 $j$ 就找到了增广路，我们取了所有左部未被标记的点，此类边被覆盖。

例题 P6062

跟上一道题其实一模一样，只是变成了求二分图最小点覆盖，改改代码就能过(双倍经验)。

二分图最大独立集

选出最多的点使这些点两两之间没有任何连边。

很显然的结论：二分图最大独立集=点数-二分图最小点覆盖。

选出一些点没有连边，就相当于选出一些点使边全被覆盖，我们删去点覆盖中的点后，任意一条边的两个点必删去其中一个，所以剩下的点就没有连边。

也就是说，一个独立集就是一个点覆盖的补集。

所以求最大独立集就相当于求最小点覆盖。

例题 P3355 P5030

这两道题也是经典模型了，只需要依题目建出二分图求独立集即可。

二分图最大权匹配

一种通用解决方法是使用费用流。(推荐)

特殊情况下可以用 KM 算法解决二分图最大权完美匹配。

KM 限制较大，一般不会用到，还不如直接学费用流来的实在（

最小环

问题

给出一个图，求由 $n(n \ge 3)$ 个节点组成的边权和最小的环。

Dijkstra解法

可以枚举每个点 $s$ 作为起始点，将这个点周围的点更新后，再把 $dis[s]$ 设为 $INF$，这样第一次从堆中取出 $s$ 时，就得到了以 $s$ 为起始点的最小环，时间复杂度 $n(n+m)\log n$。

Floyd解法

考虑 Floyd 算法本质是个 DP，我们实际用 Floyd 时压掉了一维，在最初的 Floyd 算法中， dis[k][i][j] 表示只经过编号小于等于 $k$ 的节点时，从 $i$ 到 $j$ 的最短路。

在第 $k$ 次循环开始前，dis[i][j] 存储了经过节点编号小于 $k$ 时从 $i$ 到 $j$ 的最短路，所以此时 dis[i][j]+val[i][k]+val[k][j] 构成一个环，我们用这个值更新答案，最终即可求得最小环。

int n;
int val[N][N];
int dis[N][N];

int floyd()
{
    int ans = INF;
    for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
        dis[i][j] = val[i][j];
    for(int k = 1; k <= n; k++)
    {
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            ans = min(ans, dis[i][j]+val[i][k]+val[k][j]);
        
        for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
    }
}

网络流

网络流算法都讲过了，这里就还是直接看题吧。

先来道简单的: P3872

这道题直接选不好考虑，那我们就贪心一手，先把正权值的全选上，然后减去选负权值和不满足前置关系的费用就行了，后面的部分很明显最小割可以解决，于是我们把正权值的点向 T 连流量为 a[i] 的边，S 向负权值的点连流量为 -a[i] 的边，前置关系 y 向 x 连一条权值为 d 的边，答案就是所有正权值减去最小割的代价。

再来道有意思的: P8465

这道题与 P6054 开门大吉 比较类似，我们按时间轴建出 $k$ 条链，每条链上的边即为选这个点的代价，对于一条限制，我们从 $(i,x+1)$ 向 $(j,n-y+1)$ 连一条 $INF$ 的边，求解最小割。

但是题目有一个小限制：每条链只能选一个点，我们可以给所有边整体加上一个较大值，使多选一个点的代价严格大于其他所有情况的代价就可以避免一条链选多个点了。

这时我们兴致勃勃的开始敲代码，于是在const int MAXN = ?; 处停下，看一眼数据范围 $n \le 1e5, k \le 1e4$，如果把所有链都建出来，总点数达到了 $1e9$，不能接受，需要考虑优化。

我们发现，链上无限制的一段可以被一条边权为其中最小值的边所替代，所以我们可以只建出与限制有关的点，只需要 $2k$ 个点即可解决问题。

经典传承：P4003

我真不信有人第一眼就看出来这玩意是网络流。

拿到这个题，毫无思路，先想想网络流题的经典套路，我们注意到这是个棋盘，二话不说先套上个黑白染色，于是我们就可以解决使棋盘不漏水的问题了: 把所有黑点看成源点，所有白点看出汇点，这样我们就可以用最大流判断棋盘是否漏水了。

题目还要求最少操作次数，所以用费用流解决问题。

可以看到一个格子最多能与周围四个格子相连，于是我们使用万能的拆点，将一个格子拆成一个原点和四个方向的接口点，剩下的就是通过接口点的连接来处理费用了。

又是一道题: P3731

这个题要我们求解最大团相关问题，最大团不好解决，我们可以考虑原图的补图，这样原图的最大团就对应一个补图的最大独立集。

因为一般图的最大独立集是NPC问题，我们还需要证明补图是张二分图。因为题目中提到恰好可以划分为不超过两个城市群，在补图中，一个城市群内部没有任何连边，又有两个城市群，所以这张图是一张二分图。

于是我们建立一条贸易关系，就相当于在补图中删去一条边，题目所问的即为那些边删去后会使最大独立集大小更大。

考虑最大独立集=点数-最小点覆盖=点数-最大匹配，所以我们求出最大匹配的必须边即可。

但是这个数据范围不太允许暴力寻找必须边，这时我们又有一条定理：若一条边是最大匹配的必须边，则这条边一定满流，且在残量网络中这个边的两个顶点不在同一个强连通分量中。

所以我们再敲一个tarjan求强连通分量就可以解决此题了。

Stoer-Wagner 算法

这个算法可以在 $O(n^3)$ 时间内求解无源汇最小割。

由于没有了源汇，我们重新定义最小割: 以最小代价删去一些边，使图中存在两个点不连通。

此算法基于一个非常简单的思想: 在最小割中，任意两个点 $s,t$ ，要么在同一联通块，要么处于不同连通块(废话)。

设原图为 $G$，最小割为 $C$。

1. 若 $s,t$ 在同一联通块中，则割去 $C$ 后至少有一个点 $i$ 与 $s$ 不在一个连通块内，且与 $t$ 也不再同一个连通块内，所以 $i$ 与 $s,t$ 的所有连边都必须割去，所以 $s,t$ 可以看作一个整体，共享所有的边。

   也就是说，计算完 $s,t$ 之间的最小割后，就只剩下在同一联通块中的情况了，我们可以合并 $s,t$，将其视为一个点，若所有点都合并完毕，则算法结束 。

2. 若 $s,t$ 不在同一连通块中，则我们需要求解 $s,t$ 的最小割。

我们构造一个集合 $A$，一开始 $A = \varnothing$，我们以某种顺序将点加入到集合中。

定义一个权值 $w(i)$ 为点 $i$ 与集合 $A$ 中点的连边的权值和 。

算法流程：

1. 每次选择 $w(i)$ 最大的 $i$ 加入 $A$ 中，进行 $n$ 次加入即可确定所有点加入 $A$ 的顺序，设最后一个加入 $A$ 的点为 $t$, 则任意一点 $s$ 到 $t$ 的最小割即为 $w(t)$。

2. 选出最后加入 $A$ 的两个点，并合并这两个点。

3. 合并 $n-1$ 次之后图中只剩下一个点，算法结束。

证明我不太会（逃

#include <bits/stdc++.h>
using namespace std;

const int N = 605;
const int INF = 0x3f3f3f3f;


int n, m, s, t;
bool vis[N], del[N];
int dis[N][N], w[N], ord[N];

int contract(int x)
{
    memset(vis, 0, sizeof(vis));
    memset(w, 0, sizeof(w));
    w[0] = -1;
    for(int i = 1; i <= n-x+1; i++)
    {
        int id = 0;
        for(int j = 1; j <= n; j++)
        if(!del[j] and !vis[j] and w[j] > w[id]) id = j;
        vis[id] = true; ord[i] = id;
        for(int j = 1; j <= n; j++)
        if(!del[j] and !vis[j]) w[j] += dis[id][j];
    }
    s = ord[n-x]; t = ord[n-x+1];
    return w[t];
}

int Stoer_Wagner()
{
    int res = INF;
    for(int i = 1; i < n; i++)
    {
        res = min(res, contract(i));
        del[t] = true;
        for(int j = 1; j <= n; j++)
        {
            dis[s][j] += dis[t][j];
            dis[j][s] += dis[j][t];
        }
    }
    return res;
}

signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        dis[a][b] += w;
        dis[b][a] += w;
    }
    printf("%d\n", Stoer_Wagner());
}

Prufer序列

Prufer 序列可以将一个带标号 $n$ 个节点的树用 $[1,n]$ 中的 $n-2$ 个整数表示。每棵树与其建立出来的 Prufer 序列构成一组双射。

Prufer 序列常用于组合寄数问题上。

对树建立 Prufer 序列

每次选择一个编号最小的叶子节点并删掉它，在序列中记录这个节点的父亲。

暴力是 $O(n^2)$ 的，可以用堆优化到 $O(n\log n)$，但是我们有更优秀的 $O(n)$ 构造法。

我们可以先计算出每个节点的入度(儿子数)，然后用一个指针从小编号到大编号开始扫描，遇到一个入度为 $0$ 的点就将其删去，若它的父节点变成叶子节点且编号比当前节点小，就删去它的父节点，直到不能删为止。若它的父节点变成叶子节点但编号比当前节点大，我们直接向后扫描即可，即使它是当前最小的也会在后面的扫描中第一个被处理。

for(int i = 1, j = 1; i <= n-2; i++, j++)
{
    while(in[j]) j++; pru[i] = fa[j];
    while(i <= n-2 and !--in[pru[i]] and pru[i] < j)
        pru[i+1] = fa[pru[i]], i++;
}

由 Prufer 序列还原树

可以看到，一个节点在 Prufer 序列中的出现次数，即为这个节点的入度，所以入度为 $0$ 的点就是当前树中的叶子节点。

我们仿照构造 Prufer 序列的方法，用一个指针从小编号向大编号扫描，遇到入度为 $0$ 的点则记录它的父亲为当前的 prufer 值，其余步骤与上面相同。

pru[n-1] = n;
for(int i = 1, j = 1; i <= n-1; i++, j++)
{
    while(in[j]) j++; fa[j] = pru[i];
    while(i <= n-1 and !--in[pru[i]] and pru[i] < j)
        fa[pru[i]] = pru[i+1], i++;
}

凯莱公式

完全图 $K_n$ 有 $n^{n-2}$ 棵生成树。

我们可以用 Prufer 序列证明它: 任意一个长度为 $n-2$ 的值域为 $[1,n]$ 的整数序列都可以通过 Prufer 序列对应一个生成树，所以方案数就是 $n^{n-2}$。

优化建图

没想到吧我又回来了!

经典传承: P5471

很明显是一道最短路，只不过变成了从一个点向一条矩形连边，暴力连肯定寄，考虑优化建图。

我们需要一个可以查询矩形的数据结构，可以用树套树解决，但是更简便的方法是使用 K-D Tree，但是空间只给了 125MB，无法支持我们把所有边都建出来。

于是我们可以不把图建出来，而是把所有弹跳装置存下来，因为我们可以直接用 K-D Tree 查询出能到达的节点。

由于没有负边权，我们选用比较靠谱的 Dijkstra 算法求解最短路，这时我们发现 Dijkstra 算法一个美妙的性质: 每个节点只会入队出队一次。 这个性质保证了我们每个弹跳机的查询只会进行一次，从而保证了时间复杂度为 $O(n \log n + m \sqrt{n})$。

再来一道: CF793G

又是套路的二分图匹配，但是数据范围好像有亿点大？

没关系，我们可以优化建图！区间问题很明显可以线段树优化建图，我们一开始肯定能想每个 $x$ 坐标上建一颗线段树，但是这样点数搞不好还是 $n^2$ 的。

我们可以借鉴扫描线和可持久化的思想，将矩形变为差分线段，然后保留之前的节点，只新建出有更改的节点，这样点数和边数就是 $n \log n$ 级别，刚好能通过本题。