[费用流训练] - cool's Blog

[费用流训练]

cool posted @ 2016年9月17日 17:05 in 图论 , 164 阅读

一直不会费用流,每天用单纯形骗分,被大骂一通,开始学习费用流。

费用流什么原理不是很清楚,但板子还是很好背的。

 

[方格取数]

矩阵每个元素最多取一次,从左上走到右下K次的权值最大值。

拆点,然后1条边是有费用的,流量1,其余边都是0费用,inf流量。

S向起点流K,终点向T流K。

[餐巾计划]

详见网络流24题。

拆点,i表示当天需要数,i'表示当天有多少没洗。

[bzoj3171循环格]

一个矩阵,每个格子连向一个相邻格,问至少改多少个连边,使从任意一个点出发都能回到该点。

最后一个条件即为,每个点出入度都为1。所以每个格子向原来连向的格子连0费用,1流量,其他连1费用,1流量即可。

[bzoj1070修车]

N个人修M辆车,求平均最小等待时间。

建图有点神,有点暴力的感觉。

把每个工人拆成N个点。记为A[i,j]表示第i个工人修倒数第j辆车。

每个车跟所有N*M个工人拆出的点连边。流量为1,费用为time[i,j]*k。

源和每辆车连边,N*M个点和汇连边,流量都为1,费用同为0。——by hzwer

 

bzoj2879是加强版,不过还没看懂,先留个坑。

 

[bzoj2324营救皮卡丘]

有K个人,先到了i-1点,才能走到i点,走到N点,问最短距离。

Floyd求出最短距离,且dis[i][j] = dis[i][k]+dis[k][j]的k不能比i,j都大。

又因为每个点都必须经过的,所以每个点都至少有1的流量,从S向i'流1就行了。

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee