SYC2022 Day5 图论

E1 [ZJOI2015] 幻想乡战略游戏

$n,m\le 10^5$ 。保证点权一直非负。

事实上，我们发现树的重心和边是否带权没有关系，仅仅取决于点权。如下：

$edge\cdot (size_{root}-2\cdot size_v)$ $size_v\ge\frac 12size_{root}$ $size$ $size\ge \frac 12size_{root}$ 的点。

$\sum_{i}dis(i,u)\cdot val(i)=\sum_idep_i\cdot val_i+dep_u\cdot val_i-2\cdot dep_{lca}\cdot val_i$ $O(n\log^2{n})$ 。

事实上，我们也可以使用点分治来实现这个树二分的过程，当然有点杀鸡焉用牛刀了。

E2 Codeforces 843D

给一个有向图，支持两种操作
$1$ $t$ 的最短路。
$+1$ 。
$n, m \le 10^5$ $q≤2000$ $\le 10^6$ 。

$O(m+n)$ $dis_u+e-dis_v$ ，修改时也修改在新图上，跑出新图的最短路，也就求出了原图的最短路的增量。

$x$ $x$ 。在值域特别小时，可以用桶来维护 dijdis $qm+\sum x$ 的。

E3 [SDOI2019] 世界地图

给一个网格图，相邻的点有边，边权随机。
$[l,r]$ $n \le 100, m \le 10^4 ,q \le 10^4$ 。

$O(Poly(n))$ 快速合并两个区间的 MST，我们就能维护出每个前缀的 MST 和每个后缀的 MST，从而在每次询问时也用同样的方法来合并一个前缀和一个后缀以得出答案。

假设已经知道了一个区间内的 MST，在右边界上加一条边，一定是在新形成的那个环上删去一条边。因此在它右边和另一个区间合并后，此区间内会删去的边仅仅在右边界所有点构成的虚树上。我们建出右边界上所有点的虚树，虚树上的每条边都是这条链上的最大边权；除此之外的边可以直接计入答案了，已经不可能被删去了。

$O(n\log{n}(m+q))$ 。

保证字典序最小的 2-SAT

$a_i$ $a_i = 0$ ，然后 dfscheck $j$ $j′$ $a_i = 1$ $a_i = 0$ ，再 check 一遍，如果还是不行，则无解。
$O(n(n + m))$ 的，但是求出来的解是满足字典序最小的。“取 SCC 拓扑序大的那个”的做法并不能保证这点。

E4 经典题

用最少路径数覆盖一般图的每一条边。

一个经典的结论：

半欧拉图的判定 $u$ $1$ $v$ $1$ $u, v$ $3$ 。
推论：如果所有顶点入度与出度差的绝对值之和为 2k，那么可以用至少 k 条路径将图的每条边经过一次。

$0$ ，跑出欧拉回路，并把这些额外的边断掉即可。（无向图就是把奇点两两匹配）。


xxxxxxxxxx
7
1
void dfs2(int u) {
2
    for(int &e = head[u]; e; e = next[e]) {
3
        if(vis[e]) continue; int t = e;
4
        vis[e] = 1; dfs2(to[e]);
5
        stk[++top] = t;
6
    }
7
}

E5 Codeforces 737E

$n$ $m$ $n\le 40,m\le 60$ 。

vizing 定理：

$r(G)$ $\max d_i\le r(G)\le \max d_i+1$ 。
$\max d_i=r(G)$ 。

$R_i$ $i$ $C_j$ $j$ $T=\max{R_i,C_j}$ $\max R_i,C_j$ 。

$C$ 最大的游戏机，把它分成均等两部分即可。

$m$ $n$ $T$ $T$ $T$ 。

我们也就要构造出这张新图的边染色的方案，然后删去假点，显然失去的边仅仅表示空余的时间，依然会是合法的方案。而这张新图则十分有性质，所有点的度数都相等Hall $1$ 的边）这件事情的复杂度可以接受。

也可以用最小边染色的方法来做，方法在下一题中讲解。

E6 Codeforces 212A

$k$ $i$ $w_i = \max_j a_{i,j} − \min_j a_{i,j}$ $a_{i,j}$ $j$ $i$ $n, k \le 200, m \le 5000$ 。

$w_i=1-[k|d_i]$ $k$ $\left\lceil\frac {d_i}{k}\right\rceil$ $\left\lfloor\frac {d_i}{k}\right\rfloor$ $k$ $k$ $k$ 的二分图，我们即要求它的一个最小边染色。

$O(m^2)$ $x,y$ $l_x,l_y$ $x,y$ $l_x=l_y$ $l_x$ $l_x<l_y$ $l_x$ $y$ $l_x$ $l_y$ $z$ $z$ $l_y$ $l_y$ $l_z$ vizing $\{1,2,3,4,\cdots,l_x-1\}$ $l_z$ $m\max d$ 。

E7 中国邮递员问题

$n \le 400$ 。

本质上其实是要复制一些边，使得每个点的度数都是偶数，且复制的边权和最小。显然每条边不会复制超过一遍。

考虑复制一条边的作用是什么。一个奇数点和偶数点之间连一条边，相当于把奇数点向偶数点移动了一步；而目标是一直走到另一个奇数点上，将其对撞掉。相当于，我们要把奇数点两两分组，使得彼此之间最短路的和最小。显然这些路径不相交，因为若边相交则可以交换目的地，路径总长会缩短，构成了一个类似 300iq Contest 1J 的证明。

如果是有向图，可以方便地用 KM 解决问题；但当问题是无向图时，~~看上去是一般图最大匹配~~，但实际上也可以用 KM 解决。

E8 例题

$O(n)$ ，求一个多项式做法。

我们发现完美匹配实际上可以用排列来表示，如果我们要精确地统计出每种权值和地完美匹配各有多少个，我们可以列出如下式子：

\sum_{P}\prod_{i=1}^nx^{v(i,P)}

$x$ $0$ $O(n^5)$ 。

E9 稳定婚姻问题

$n$ $n$ $n\le 2000$ 。

根据生活经验，这个问题一定有解。因此我们采取类似增广路算法的方式，具体如下：


xxxxxxxxxx
9
1
for (u = 任一个暂未匹配的男生)
2
    for (v = u 未曾尝试过的好感度最大的女生)
3
        // u 向 v 这个女生发起尝试
4
        if (v 单身) 直接匹配 u 和 v
5
        else
6
            令 w = v 当前的男朋友
7
            if v 对 u 更加喜欢
8
                u 的尝试成功，匹配 u 和 v，并将 w 重新丢回单身男生的序列
9
            else u 的尝试失败，继续尝试下一个女生去了

$O(n^2)$ 。

E10 Codeforces 1161F

$1 \sim n$ $n + 1 \sim 2n$ $n \le 2000$ 。

我们发现后手必胜。

$(A-B)$ $(C-D)$ $A$ $B$ $B$ $C$ $BC>AB$ $B$ $C$ $C$ $D$ $CD<BC$ 。也就是说，后手这一步一定能走。

E11 Codeforces 1307G

$n$ $q$ $x$ $a_i$ $∑a_i \le x$ $a_i$ $1$ $n$ $n \le 50$ $q, x \le 10^5$ 。

题中这种最短路的线性规划形式和费用流的线性规划形式是对偶的。下面我们来手把手求这个线性规划的对偶。

$y_i$ $1\rightarrow i$ $x_{u,v}$ $(u,v)$ $w_{u,v}$ $(u,v)$ 原来的长度。我们可以得出如下的线性规划：

\begin{cases} \operatorname{maximize} y_n-y_1\\ y_v\le y_u+x_{u,v}+w_{u,v}\\ \sum_{u,v}x_{u,v}\le X\\ x_{u,v}\ge 0 \end{cases}

线性规划的对偶形式相当于把这个矩阵给转秩一下。我们给上面这个线性规划的每一行都乘上一个数，表示转秩后的自由元（转秩后的自由元个数等于原来的限制个数），并且都转成小于等于的形式，以符合对偶需要的性质，方便接下来的书写。

\begin{cases} \operatorname{maximize} y_n-y_1\\ a_{u,v}\cdot y_v\le a_{u,v}\cdot (y_u+x_{u,v}+w_{u,v})\\ -b_{u,v}\cdot x_{u,v}\le 0\\ c\sum_{u,v}x_{u,v}\le cX \end{cases}

$\ge$ $\le$ $=$ $\le$ ）。

于是我们就可以来转对偶了。目标函数部分，就是原线性规划的常数项的和（需要先移项到右边）：

\operatorname{minimize} \sum_{u,b}a_{u,v}\cdot w_{u,v}+cX

$y_u$ 的限制条件：

\sum_{v}(a_{u,v}-a_{v,u}) = \begin{cases} 1 & u=n \\ -1 & u=1 \\ 0 & \mathtt{else}\end{cases}

$x_{u,v}$ 的限制条件：

c-a_{u,v}-b_{u,v}=0

提完了之后添上不等式的限制条件：

a_{u,v},b_{u,v},c\ge 0

$b$ $b$ $c=\max_{a_{u,v}}$ $c$ $0$ $c$ $c\ge a_{u,v}$ ，所以我们前面的这种构造已经是最优的了。于是变成了这样一个问题：

\begin{cases} \operatorname{minimize} \sum_{u,b}a_{u,v}\cdot w_{u,v}+X\cdot \max a_{u,v}\\ \sum_{v}(a_{u,v}-a_{v,u}) = \begin{cases} 1 & u=n \\ -1 & u=1 \\ 0 & \mathtt{else}\end{cases}\\ a_{u,v}\ge 0 \end{cases}

$a$ $u$ $v$ $1$ $w_{u,v}$ $\max{a_{u,v}}=1$ $=flow$ $a$ $flow$ ，就可以得到本问题的符合流平衡的方程：

\begin{cases} \operatorname{minimize} \frac 1{flow}\cdot\left(\sum_{u,b}a_{u,v}\cdot w_{u,v}+X\right)\\ \sum_{v}(a_{u,v}-a_{v,u}) = \begin{cases} flow & u=n \\ -flow & u=1 \\ 0 & \mathtt{else}\end{cases}\\ a_{u,v}\ge 0 \end{cases}

$\frac {cost-cost_0}{flow-flow_0}$ $\frac{cost_0}{flow_0}$ $cost$ $flow$ $\frac 1{flow}$ $X$ 的斜率越来越小。这是一个斜率越来越小且截距越来越大的直线集，对我们有用的就是这个直线集的下包络线。对于每次询问，都遍历每次增广，并求出其在包络线上的最低点即可。