2022.5.28 集训：图论
posted on 2022-05-28 12:02:29 | under 题解 | source
感谢 vjudge.net 提供技术支持。
CF771A Bear and Friendship Condition
题意
给定 $n$ 个点 $m$ 条边的图，描述了社会上 $n$ 个人之间的朋友关系。
我们说这个社会关系是紧密的，当且仅当：
- 若 $a$ 和 $b$ 是朋友，且 $b$ 和 $c$ 是朋友，那么 $a$ 和 $c$ 也是朋友。
请判断给出的社会关系是否紧密。
题解
结论：社会关系紧密，当且仅当每个连通块是完全图。
证明：考虑只有三个点，是一个完全图。加入一个点并往三角形里连一条边，就会不得不补齐剩下所有 $n$ 条边，因此它一定是完全图。
代码
https://codeforces.com/contest/771/submission/158658564
CF449B Jzzhu and Cities
题意
一个国家有 $n$ 个城市，其中第 $1$ 个城市是该国家的首都。
有 $m$ 条双向道路 $(u,v,x)$，表示城市 $u$ 和 $v$ 之间有一条长度为 $x$ 的双向道路。
有 $k$ 条双向的高速铁路 $(s,y)$，表示城市 $1$ 和城市 $s$ 之间有一条长度为 $y$ 的双向高速铁路。
输入数据保证，从首都 $1$ 城市出发，可以抵达其它所有城市。
现在这个国家为了节省开支，决定关闭一些高速铁路，但不能影响交通效率。
现在你需要回答，最多删除多少条高速铁路，能使得从 $1$ 城市出发，到其它各个城市的最短路径长度不变。
题解
- 带着全部边跑最短路，记 $1$ 到 $u$ 的最短路为 $d_u$。
- 考虑一条普通道路 $(u,v)$ 能不能走到最短路，即 $d_u+e(u,v)\leq d_v$。如果能，说明关于 $v$ 的高速路全部没用（即 $d_v$ 不需要用到高速路了，这些高速路可以割断）。
- 注意处理重边。
代码
https://codeforces.com/contest/449/submission/158665485
CF1340C Nastya and Unexpected Guest
题意
Denis 要去见他的女朋友，他的家在 $0$ 号节点，那个女孩子的家在 $n$ 号节点。
相邻的两个节点，即 $i$ 号节点和 $i+1$ 号节点之间的距离是 $1\ \tt m$，行走时间需要 $1\ \tt s$。
由于交通复杂，一路上有红绿灯，绿灯会持续 $g$ 秒，而红灯会持续 $r$ 秒，循环往复。
由于心急如焚，所以若非受限，Denis 一刻都不愿意停下来，只要是绿灯，他要求自己必须保持行走。
但是并不是所有地方都能停下来等待红灯。
路上有 $m$ 个指定路口设置了等待区，在恰好红灯亮起的时候，他必须恰好到达这些路口之一，否则可能飞来横祸。
Denis 发现，如果一直径直向前，在红灯亮时，他未必能恰好处于路口，所以他也不会奋勇无前。
具体来说，每到一个路口，他都可以选择往正方向或者反方向行走。
给定 $m$ 个路口的位置，问最优策略下，他需要多少秒到达 $n$ 号节点，无法到达输出 $-1$。
题解
- 发现路口是没用的，既不能停又不能转向，所以只考虑安全岛。在安全岛只能走到上一个/下一个安全岛。
- 但是有红灯的存在，向另一个安全岛转移时可能会挂在路中间。所以我们在安全岛额外记录一个状态 $t$，表示距离绿灯亮起已经过了多久。显然只有 $O(mg)=10^7$ 个状态。
- 考虑转移：$f(u,t)$ 可以转移到 $f(u+1,t+d_{u+1}-d_u)$，当且仅当 $t+d_{u+1}-d_u\leq g$，即绿灯仍亮或刚好卡在红灯。注意取等的情况，这时候 Denis 要等一轮红灯，我们记录他等红灯的次数加一。往上一个安全岛同理。
- 开始转移，使用 01-bfs 实现，每次从队首取出一个状态，转移时如果加一，那么放到队尾，否则放到队首，本质上是维护它的单调性。
- 统计答案，按照题意取个最小值，注意 $f(m,0)$ 的处理，不需要等多一个红灯。
代码
https://codeforces.com/contest/1340/submission/158668062
ABC245G Foreign Friends
题意
给定 $n$ 个人，以及他们的国籍，国家编号是 $[1,k]$。
其中有 $l$ 个是明星，备受欢迎。
开始这 $n$ 个人互不相识。
但其中存在 $m$ 种关系，可以通过金钱疏通。
具体来说，会给出 $m$ 个 $(u,v,w)$ 组合，表示可以花费 $w$ 的价钱让 $u$ 和 $v$ 互相认识。
这些人都很虚荣，他们都想认识国际明星。
问对于每个人，至少需要花费多少钱打造关系网，才能（直接或间接）认识一个非本国的明星。
题解
方法一：二进制分组
考虑把国籍拆位，对于某一位，把这一位是 $1/0$ 的明星用超级源点绑起来，和原图一起跑最短路，再更新这一位是 $0/1$ 的人的答案。
证明：两个数不相等，它们一定至少有一位的二进制不同。在本题中，可能是 $0$ 认识了 $1$，$1$ 认识了 $0$，两种情况都有可能发生，都要跑一次。时间复杂度为 $2\log n\times m\log m=O(n\log^2 n)$。
方法二
将题意转化为：求认识两个不同国籍明星所需最小花费，记为 $d_u,d'_u$。先一遍最短路跑出 $d_u$。为了保证 $d_u,d'_u$ 国籍不同，可以用类似次短路的方法求出 $d'_u$。
代码
https://atcoder.jp/contests/abc245/submissions/31991139（方法一）
ABC244G Construct Good Path
题意
给定 $n$ 个点和 $m$ 条边的无向连通图。
给定 $0$ 和 $1$ 组成的序列 ${s_i}$。
要求一个长度不超过 $4n$ 的路径序列 ${a_i}$，使得：
- $a_i$ 和 $a_{i+1}$ 是相连的，即 ${a_i}$ 是图上某条路径；
- 第 $i$ 个点在这个序列中出现的次数的奇偶性和 $s_i$ 一致。
题解
经典套路：对于无向连通图，可以求出它的任意一棵生成树，以简化原问题。
所以，我们先求任意一棵生成树。dfs 过程中，记录欧拉环游序（回溯时记录），如果遍历完 $u$ 的儿子后不满足限制条件，就往上走再下来（$u\to fa_u\to u$），改变 $u$ 的奇偶性，同时把限制条件往上移。最后到根无路可走，直接撤销最后一步。欧拉环游序长度为 $2n-1$，调整每个点最多 $2n$，符合长度限制。
代码
https://atcoder.jp/contests/abc244/submissions/31991892
CF269C Flawed Flow
题意
现在有一个 $n$ 个点 $m$ 条边的无向图。它原本代表了一个网络流图，可是现在所有边的方向都丢失了，仅剩下流量。你需要给每个边规定一个方向，使得这个图成为一个合格的网络流图。
“合格”需要满足以下几个条件：
- $1$ 号点是源点，没有入度；$n$ 号点是汇点，没有出度。
- $2\cdots n-1$ 的每一个点，都满足入度之和等于出度之和。
- 定向好的有向图中没有环！特别注意第三点。
现在你需要给出这样一个定向方案，如果有多个，随意给出一个合法的即可。图中无自环和重边，且保证有解。
题解
限制二需要我们满足入度之和等于出度之和，那么我们可以提前算出这个值，用临边之和 $\times \frac{1}{2}$ 即可算出。
注意到题目要求这个有向图没有环且保证有解，考虑直接拓扑排序，一个点的入
度满了就入队，这样一定能遍历所有点和边。
证明：感性理解，有矛盾说明图中有环。
注意源点和汇点的流量。
代码
https://codeforces.com/contest/269/submission/158678780
ABC241G（待补）
枚举答案，贪心全赢，网络流，S指向比赛流量为1，比赛指向人两边流量为1，人指向汇点为赢场限制，如果网络流有解则枚举者为答案
CF317C Balance
题意
有 $n$ 个水桶编号为 $1\sim n$，每个水桶的容量为整数 $v$。水桶之间有 $e$ 条双向管道（可能重复），一次操作可以从一个水桶通过管道输送任意非负整数量的水到另一个水桶，但要保证任意时刻水桶中的水量不超过容量。现给定一个初始局面 ${a_i}$（表示第 $i$ 个水桶的水量为 $a_i$ ）和一个目标局面${b_i}$，问是否可以在 $2n^2$ 次操作内从初始局面到达目标局面。如果可以输出方案，否则输出 NO
$1\le n \le300,1\le v \le 10^9,0\le e \le50000,0\le a_i,b_i\le v$。
题解
先判无解：一个连通块的水不够用或太多了，即 $\sum a_i\neq\sum b_i$，就无解。大胆猜测剩下的情况有解。
像 ABC244G 一样，我们先对图求一棵生成树。dfs 遍历每一个节点，考虑自底向上，先满足叶子的要求，然后把叶子杀了，这样不会影响答案。考虑怎么满足叶子的要求，其实是暴力：
- 从这个叶子 $tar$ 出发，再遍历这棵树；
- 分类讨论：
- 若 $a_{tar}<b_{tar}$，叶子需要水，自底向上给它抽水，每个节点都抽它的子节点，抽到 $tar$ 一定有水。
- 若 $a_{tar}>b_{tar}$，叶子太水了，请求它的子节点帮它接水。注意可能它的子节点全都满了，因此需要反向操作，自底向上抽它父亲的水，叶子肯定有空可被抽。
过于抽象，给个代码：
void trans(int u,int tar,int mode=0,int fa=0){//mode=a[tar]>b[tar]
for(int i=g.head[u];i;i=g.nxt[i]){
int v=g[i].v;
if(vis[v]||v==fa) continue;//vis[v] 记录 v 有没有符合要求
trans(v,tar,mode,u);
}
if(u==tar) return vis[u]=1,void();
if(mode){
if(fa==tar) print(fa,u,min(a[fa]-b[fa],k-a[u]));
else print(fa,u,min(a[fa],k-a[u]));
}else{
if(fa==tar) print(u,fa,min(b[tar]-a[tar],a[u]));
else print(u,fa,min(k-a[fa],a[u]));
}
}
代码
https://codeforces.com/contest/317/submission/158930667
输出很烦，不想写结构体，我们可以使用 sprintf 的特性，它返回输出字符个数，于是我们可以这样写：
int cnt;
char buf[3000010],*o=buf;
void print(int u,int v,int k){
cnt++;
o+=sprintf("%d %d %d\n",u,v,k);
}
printf("%d\n%s",cnt,buf);
CF416E President's Path
题意
给定 $n$ 个点 $m$ 条边的带权无向简单图。
求：对于每一对 $(s,t)(1\leq s<t\leq n)$，有多少条边，存在于至少一条从 $s$ 到达 $t$ 的最短路中。
题解
定义符号 $s\to t$ 表示 $s$ 到 $t$ 的最短路。推论：$u$ 在 $s\to t$ 上，当且仅当 $s\to u\to v=s\to t$。
- 一遍 floyd 复杂度 $O(n^3)$，枚举 $(s,t)$。
- 试图枚举每条边，复杂度是 $O(n^4)$，不好。可以分开算吗？
- 考虑换一个枚举顺序。求一个 $h(s,u)$，表示 $u$ 有多少条出边 $(u,v)\in G$ 落在 $s\to u$ 上，也就是 $v$ 在 $s\to t$ 上，复杂度 $O(n^3)$。
- 计算答案时，枚举点 $u$，如果 $u$ 在 $s\to t$ 上，则它的出边 $(u,v)\in G$ 也在 $s\to t$ 的最短路上，证明：$s\to v\to u\to t=s\to u\to t=s\to t$。这玩意我们已经算过了，是 $h(s,u)$，复杂度 $O(n^3)$
启发：优化复杂度时，可以减少枚举变量，重复使用信息。
代码
https://codeforces.com/contest/416/submission/158682007
CF1610F Mashtali: a Space Oddysey
题意
给定一张含 $n$ 个点 $m$ 条边的无向图，结点编号为 $1$ 到 $n$。
每条边有边权 $w_i$，而 $w_i$ 只能等于 $1$ 或 $2$。蓝想要给每条边定向，使得图尽可能的可爱。
图的可爱程度定义为图中好的结点的数量。一个结点 $v$ 是好的，当且仅当令 $d^+(v)$ 为 $v$ 所有出边的权值和，令 $d^-(v)$ 为 $v$ 所有入边的权值和，有 $|d+(x)-d-(x)|=1$。
试着帮蓝找到图的最大可能可爱程度，并且给出任意一种构造方案。
输入中，蓝会在第一行给出 $n$ 和 $m$，之后 $m$ 行每行依次给出 $u_i,v_i$ 和 $w_i$，其中前两个数代表边 $i$ 连接的两个结点，而 $w_i$ 则代表边 $i$ 的边权。
输出中，在第一行，你应该输出图的最大可能可爱程度。在输出的第二行，为了告诉蓝你的构造方案，你需要给出一个字符串 $s$，其中若 $s_i=1$，则代表边 $i$ 被定向为从 $u_i$ 到 $v_i$，而 $s_i=2$ 则代表边 $i$ 被定向为从 $v_i$ 到 $u_i$。
本题数据满足：$1 \leq n,m \leq 3\times10^5,1 \leq u_i,v_i \leq n,w_i\in{1,2}$。
题解
构造欧拉回路。以下所说的「度」均指边数。
考虑欧拉回路有个什么性质？每个点的出度等于入度。可以这样说：进入一个点，马上出去，对应题意就是抵消了。我们希望把 $1,1$ 或者 $2,2$ 逐个抵消，最后剩下：
- $\varnothing$，即偶数个 $1$ 和偶数个 $2$，不符合条件。
- ${1}$，即奇数个 $1$ 和偶数个 $2$，符合条件。
- ${2}$，即偶数个 $1$ 和奇数个 $2$，不符合条件。
- ${1,2}$，即奇数个 $1$ 和奇数个 $2$，符合条件。
看上去很棒，那么开始建图：
- 目标：
- 所有点的度为偶数。
- 尽量满足符合条件的点。
- 不要求连通，可以分开跑。
- 做法：
- 为了实现抵消，我们把边权为 $1$ 和 $2$ 的分开建图。
- 现在有 $2n$ 个点，如果点 $u$ 度为奇数，我们连一条边 $(0,u)$。
- 注意到图中度为奇数的点只有偶数个。因为每条边会给两端增加一度，试图反证就能证明。所以点 $0$ 的度为偶数。
- 正确性：
- 符合条件的「奇数个 $1$」，最后的 $1$ 可以乱连。
- 符合条件的「奇数个 $1$ 和 $2$」，令这个点是 $u_1,u_2$，它们都往 $0$ 上连边，那么抵消完后 $u_1\to 0\to u_2$，或者 $u_2\to0\to u_1$，刚好满足了要求。
- 不符合条件的，为什么要考虑？弃之。
做完了。
代码
http://codeforces.com/contest/1610/submission/159216969
/*
A:连通块是完全图
B:全部边跑dij，考虑普通边能不能更新即d(u)+e(u,v)<=d(v)，能就说明高速路能拆
C:每个路口拆成1e3个点，到路口u时绿灯亮了t秒，经过了d(u,t)个红灯，边权为到下一个路口时是不是红灯，01bfs
D:
1.二进制分组，对于每一位，将超级源点连向这一位是0的点，以源点为起点跑最短路，更新这一位是1的点
2.求认识两个明星所需最小花费，先跑出d1[u]，那么d2[u]=min{d1[v]+e(v,u),d2[v]+e(v,u)}(f[v]!=f[d1[u]])
E:求任意生成树，暴力dfs，遍历完u的所有儿子，如果不满足就往上走两遍把矛盾往上移，最后到根就撤销最后一步
F:求出每个点应有入流量（所有流量/2），拓扑，到了一个点满了就入队，有矛盾就会有环
G:枚举答案，贪心全赢，网络流，S指向比赛流量为1，比赛指向人两边流量为1，人指向汇点为赢场限制，如果网络流有解则枚举者为答案
H:有解条件为连通块内sum(ai)=sum(bi)，每一个连通块求生成树，接着
1.枚举树中每一个点，动用整棵树满足它需要的水，再把多余的水拉上去
2.枚举叶子节点，暴力满足它，并杀掉这片叶子
I:floyd O(n^3)，枚举u在不在s->t的最短路上记为g(s,t,u)，枚举u有多少临边落在s->u的最短路上记为h(s,u)，枚举f(s,t)并合并g,h
J:构造欧拉回路
*/