BZOJ 3931 [CQOI2015] 网络吞吐量

发布于 2017-05-19  110 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3931

题意:n 个点,m 条边,边有边权,点有流量上限,流量沿着最短路走,求最大流...


水题啊水题... 因为奇怪的错误狂 WA 不止... 坑了我一上午的人生... 先跑一边最短路,看看有哪些路径是在最短路上的,建新图,对于点 i,拆点成入点\(x_i\) 和出点\(y_i\),在它们间连一条流量为点权的边来限制流量... 然后就结束了...

注意需要开 long long.. 代码如下:

 


一个非常弱的准退役OIER