[HDOJ3667 Regional Harbin Transportation]【拆边费用流】

【题目大意】
求一最小费用流,边的费用是a*flow^2。
每条边的容量<=5
【算法分析】
早在我初三的时候,刚刚学习完KM算法,老师给我们做得一套模拟题里就有这个模型。。。是什么工作分配的。当时还很菜很菜,然后居然很奇葩地想到拆点然后套KM,就过了,然后和我一起学的童鞋们都毫无想法,那时兴奋了我一整天=_=。
具体思路如下:
(x+1)^2-x^2=2x+1…
就是每次加2x+1,就能使和依次为每一个完全平方数。
然后2x+1又是递增的。
那么对每一格容量拆成容量为1,费用为2x+1的边,做最小费用流就可以了。
【其他】1Y。
【CODE】
http://xiudaima.appspot.com/code/detail/1684003

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注