需要思考才能转化缩点问题（用猜的结论验证结论）：Gym - 103427H
需要思考才能转化缩点问题（用猜的结论验证结论）：Gym - 103427H
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/134366564
https://vjudge.net/contest/593228#problem/E
首先大胆猜结论，偶数条边全选，奇数条边有一条不选，那哪条呢？
考虑找桥。如果一条边不是桥，那么删掉后恰好偶数条边，符合我们猜的结论。
如果是桥，那么必须满足分成的两个连通块的边数都是偶数，这样才能满足我们猜的第一个结论。
然后缩点后在树上跑一遍即可。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2021-11-28
【Loj #10098. 「一本通 3.6 例 1」分离的路径】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15615609.html 题目链接 首先，环内的节点必然可以至少存在两条路径到达，所以我们不用考虑环内的节点，可以先对无向图缩点。 剩下的节点必然构成一棵树，我们只需要将叶子节点两两配对。因为这样其上面的所有父亲节点都可以通过它下面的叶子节点形成环。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515...
2021-11-17
【P2169 正则表达式】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15569311.html 题目链接 这道题正好让我在noip前复习了一次缩点。 首先题目里有这么一句话。 另外，如果存在A到B的连接的同时也存在B到A的连接的话，那么A和B实际上处于同一局域网内，可以通过本地传输，这样花费的传输时间为0。 这不就是在提示我们要用缩点吗？ 他希望知道从他的电脑（编号为1），到小X的电脑（编号为n）所需要的最短传输时间。 最短时间，就是弄个最短路就行。由于缩点后是DAG图，所以可以用dp。 我用的是dp。（其...
2021-11-29
【Loj #10102. 「一本通 3.6 练习 3」旅游航道】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621787.html 题目链接 题目中对主要航道定义是这样的： 如果某一条航道的删除使得一些星球不能到达，那么这条航道是不能删除的，称之为「主要航道」。 这说明了什么？ 说明了主要航道就是桥。 然后题目就是求桥的个数。 模板题。 Code 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455...
2021-11-29
【Loj #10100. 「一本通 3.6 练习 1」网络】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15620690.html 题目链接 题目就是给出一幅图，求其割点个数。 由于 n⩽100n\leqslant 100n⩽100，所以可以暴力删点。 当然也可以跑割点。 (感谢crx老师教我割点模板) 暴力Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636...
2021-12-09
【SSOJ2625: 哪些路不能修】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15669522.html 题目 一个有n个景点（入口）、m条单向道路的旅游胜地，单向是不友好的，因为这会让游客走很多冤枉路，而且从同一个入口出发，往不同方向走，能游玩的景点数目可能不同。于是，善良的Bob决定将道路全部改造成双向的，让每一个入口能逛的景点数量都确定下来，并制作景点数目表，让游客清楚地知道各个入口的景点数。但是，如果全部改成双向边之后，还需要修路，就可能导致景点数目表不正确。如果要景点数目表正确，请问哪些路是不能修的？ 思路 这题的...
2021-12-01
【Loj #10104. 「一本通 3.6 练习 5」Blockade】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15629936.html 题目链接 首先这个点删去之后必然与剩下 n−1n-1n−1 个点失去相连。 如果这个点能使其它点失去相连，说明这个点为割点。 然后统计一下每个儿子与父亲的影响即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666...