Transportation (UVa Live Archive Asia - 2010 Harbin)
問題
N頂点,辺数Mの有向グラフGが与えられる。各辺には容量cと重みaが与えられる。この辺には整数の水を流すことができ、かかるコストは「a*水を流した量^2」になる。頂点1から頂点Nまでkの水を流すにはいくらのコストが必要か？
1<=N<=100
1<=M<=5000
0<=k<=100
0
解法
辺の容量に応じて、容量が1で重みがそれぞれa,3a,5a,7a,9aの辺に分割して最小費用流をすれば良い。
