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

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

[方格取数]

矩阵每个元素最多取一次，从左上走到右下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就行了。