比赛链接

AC 5题，Rank 19th

I是我认为相当精彩的一道题。赛场上是用了一个网络流假算法，结果因为数据太水侥幸通过。

首先d=1 or d=2意味着残存图是由线段和环组成的。网络流/费用流的想法其实在这题来说相当自然。我赛场上的想法是每个点拆出入两点，源点连向左奇数点，右奇数点连向汇点，再按照读入的边，左往右连边。最后d=2的点右往左连cap=2的边。到达一个点的边被赋予-1的费用。我以为只要求出最小费用最大流，一单位流就可以代表了线段，费用取反，看和度数之和是否相等，就能判断了。

事实上这个想法漏洞百出，首先根本没有解决好d=2成环的问题。另外仔细想想，

by cmx