2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_1
这是本文档旧的修订版！
简况
AC 5题，Rank 19th
总结与反思
cmx
lpy
xsy
题解
I. 1 or 2
I是我认为相当精彩的一道题。赛场上是用了一个网络流假算法，结果因为数据太水侥幸通过。
首先d=1 or d=2意味着残存图是由线段和环组成的。网络流/费用流的想法其实在这题来说相当自然。我赛场上的想法是每个点拆出入两点，源点连向左奇数点，右奇数点连向汇点，再按照读入的边，左往右连边。最后d=2的点右往左连cap=2的边。到达一个点的边被赋予-1的费用。我以为只要求出最小费用最大流，一单位流就可以代表了线段，费用取反，看和度数之和是否相等，就能判断了。
事实上这个想法漏洞百出，首先根本没有解决好d=2成环的问题。另外仔细想想，
by cmx
补题
2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_1.1594606487.txt.gz · 最后更改: 2020/07/13 10:14 由 maxdumbledore
