今天做题的时候碰到了一道网络流的题竟然没有做出来，甚至到现在还是没有弄懂的囧，实在是惭愧，所以现在好好理理网络流了o(╯□╰)o。
hdu1532
题意：纯求最大流。
题解：以1为源点，n为汇点建边。
hdu1533
题意：在一个栅格地图上有n个的小男人和n个房子，在每一个单位时间内每个小的人可以移动一个单位的一步到相邻的点，无论是水平的还是垂直的。对于每一个小人，他每移动一步，你需要支付1美元的旅行费用，直到他进入一所房子。限制条件是每间房子只能容纳一个小人。 你的任务是计算发送这n个不同的小人到n个不同的房屋所需要支付的最低金额。
题解：最小费用流。该题中距离的定义是两点横坐标差的绝对值和纵坐标差的绝对值之和，并且我们可以看到小人的数目和房子的数目是相等的（设为n），则我们将每个小人与每个房子之间建立一条容量为1，费用为彼此之间距离（是按照上述定义的距离）的流；同时我们设定一个超级源和超级汇，从超级源连接到每一个小人容量为1，费用为0的流；从每个房子连到超级汇一条容量为1，费用为0的流，最火从超级源到超级汇求一下最小费用流即得到答案。



今天就到这里了，谢谢关心: ）   2012/9/6 8:55 by Mr.一首歌