洛谷3288 [SCOI2014]方伯伯运椰子
Luogu 分析 显然调整后总交通量不变是最佳的，因为不能减少，并且增加的话费用一定会变大。 发现压缩操作很像网络流中的退流，扩充操作很像网络流中的增广。 所以对于原图中的每条边 $(u,v,a,b,c,d)$ ，新建两条边： $v\to u$ ，边权为 $a-d$ （如果 $c=0$ ，不要建这条边）。对应压缩。 $u\to v$ ，边权为 $b+d$ 。对应扩充。 发现在这张图跑，经...
Luogu 分析 显然调整后总交通量不变是最佳的，因为不能减少，并且增加的话费用一定会变大。 发现压缩操作很像网络流中的退流，扩充操作很像网络流中的增广。 所以对于原图中的每条边 $(u,v,a,b,c,d)$ ，新建两条边： $v\to u$ ，边权为 $a-d$ （如果 $c=0$ ，不要建这条边）。对应压缩。 $u\to v$ ，边权为 $b+d$ 。对应扩充。 发现在这张图跑，经...