本题数据也太几把水了

SP4227 MSE06I - "Shortest" pair of paths

ivyjiao @ 2025-01-11 10:31:22

rt，我在第一遍 AC 此题的时候，错了两个地方，然后我在写题解的时候发现了：

  1. 把无解的条件判成了最大流 \neq 2，正确的应该是 <2。
  2. 拆点之后忘了把入点和出点之间连边，这也能过。

然后今天在写 P2153 [SDOI2009] 晨跑 的时候，又发现一个问题：连普通边的时候要把出点和入点相连，而不是入点和入点相连。

by ruik @ 2025-01-11 10:33:42

标题过于文明了。

by jason_sun @ 2025-01-11 10:44:07

没道理大于2吧

by jason_sun @ 2025-01-11 10:47:00

你要不看看你拆的点有没有用到

by jason_sun @ 2025-01-11 10:48:19

@ivyjiao

G[u].push_back({v,1,G[v].size(),f});
G[v].push_back({u,0,G[u].size()-1,-f});

你全程就没用拆的点

by SUPER_ZJC @ 2025-01-11 10:49:38

最有素质的一集

by jason_sun @ 2025-01-11 10:50:26

@ivyjiao

hack

7 8 
0 1 0
0 2 0
1 3 0
2 3 0
3 4 0
3 5 0
4 6 0
5 6 0

显然无解

by WGYPH0 @ 2025-01-11 10:51:10

本讨论标题太极吧黄了

by ivyjiao @ 2025-01-11 10:58:24

@jason_sun 这个问题就是我刚发现的啊

答案是不是 Not Possible

by jason_sun @ 2025-01-11 10:59:21

1

|