CF1468J Road Reform 题解 link CF1468J Road Reform 题面翻译 给定一个有 n n n 个节点， m m m 条无向带权边的图，和一个参数 k k k，第 i i i 条边权值为 s i s_i si​。 现在你要保留这个图中的 n − 1 n-1 n−1 条边使得这个图变成一棵树，然后你可以对这棵树上的任意边进行修改，每次修改可以使这

Tourist Reform 题解 很容易发现，对于任意一个边双连通分量，一定存在一种方法使得这个连通分量内的任意两点可以互相到达。 于是将连通分量缩点后我们得到了一棵树，因为总共只有条边，所以必定有一个连通分量无法到达其它的连通分量，而若将它作为树的根，将所有的儿子连向它的父亲，则其余点一定可以到达它，其价值一定比它大。为了使最小价值最大，我们需要选取整体价值最大的一个连通作为根。 由于

第一次打线上赛，1456分来着，感觉自己模拟题做的不怎么样，总是想复杂，而且写代码慢的要死，这套题说实话还算简单，但只A了两道，其他的题都很基础，这题欧拉通路我刚好不会，所以写一下。 题意： n个城市之间m条双向道路，现在把双向道路变成单向，求让出入度相同的城市最多的路线图。 要点： 这题就是个欧拉通路问题，因为要把双向变成单向，所以原本的出度如果是奇数，说明这个顶点的入度和出度不相等，原