关于一个 dp

学术版

喵仔牛奶 @ 2023-01-16 18:17:59

本蒟蒻在求解 DAG 上的最大流时自己 yy 了一个 dp：

设 f_u 为到 u 的最大流，然后 f_{u}=\sum_{v\to u}\min\{f_v,w\}，w 是该边的权值。

求一个反例，如果楼主太笨了轻喷。

by Tokido_saya @ 2023-01-16 18:20:43

这怎么可能对？

s=1 t=5
1 2 1
2 3 1
2 4 1
3 5 1
4 5 1

by 喵仔牛奶 @ 2023-01-16 18:22:14

@Tokido_saya 等等，我好像对最大流有点理解问题。。。。

by 喵仔牛奶 @ 2023-01-16 18:23:17

好了，此贴完结。

结论：楼主没有发现一个点流出的流量有限。

by Tokido_saya @ 2023-01-16 18:23:18

对啊，你那是个锤子的最大流

by 喵仔牛奶 @ 2023-01-16 18:24:12

@Tokido_saya thanks

|