网络流专题.pptVIP

poj 2112 Optimal Milking 有K台挤奶机器和C头牛(统称为物体），每台挤奶机器只能容纳M头牛进行挤奶。现在给出dis[K + C][K + C]的矩阵，dis[i][j]若不为0则表示第i个物体到第j个物体之间有路，dis[i][j]就是该路的长度。（1 = K = 30,1 = C = 200） 现在问你怎么安排这C头牛到K台机器挤奶，使得需要走最长路程到挤奶机器的奶牛所走的路程最少，求出这个最小值。 Sample Input 2 3 2 // K C M 0 3 2 1 1 3 0 3 2 0 2 3 0 1 0 1 2 1 0 2 1 0 0 2 0 Sample Output 2 利用Floyd算法求出每个奶牛到每个挤奶机的最短距离。 则题目变为： 已知C头奶牛到K个挤奶机的距离，每个挤奶机只能有M个奶牛，每个奶牛只能去一台挤奶机，求这些奶牛到其要去的挤奶机距离的最大值的最小值。 网络流模型： 每个奶牛最终都只能到达一个挤奶器，每个挤奶器只能有M个奶牛，可把奶牛看做网络流中的流。 每个奶牛和挤奶器都是一个节点，添加一个源，连边到所有奶牛节点，这些边容量都是1。 添加一个汇点，每个挤奶器都连边到它。这些边的容量都是M。 网络流模型： 先假定一个最大距离的的最小值 maxdist, 在上述图中，如果奶牛节点i和挤奶器节点j之间的距离= maxdist,则从i节点连一条边到j节点，表示奶牛i可以到挤奶器j去挤奶。该边容量为1。该图上的最大流如果是C(奶牛数），那么就说明假设的 maxdist成立，则减小 maxdist再试 总之，要二分 maxdist, 对每个maxdist值，都重新构图，看其最大流是否是C，然后再决定减少或增加maxdist hdu 4322 candy 有N颗糖果和M个小孩，老师现在要把这N颗糖分给这M个小孩。每个小孩i对每颗糖j都有一个偏爱度Aij，如果他喜欢这颗糖，Aij = 2，否则Aij = 1。小孩i觉得高兴当且仅当ΣCij×Aij = Bi，j=1,2,…,N，若他分得了糖j，Cij = 1，否则Cij = 0。问能否合理分配这N颗糖，使得每个小孩都觉得高兴。（1 = N = 100,000, 1 = M = 10, 0 = Bi = 1,000,000,000） Solution 可以很明显的想到一个类似于上题的模型。 如果小孩i喜欢糖j addedge(i, j, 2) else addedge(i, j, 1)。 但是注意，这样直接最大流是无法进行处理的，因为你无法强制流去流2。 思考： 如果一颗糖只造成了1的贡献，那么其实随意一颗糖都可以。 所以我们可以不管造成1贡献的糖，只去处理会造成2的贡献的糖。 Solution 模型有2层： 糖j 小孩i 如果小孩i喜欢糖j j-i 容量1 每个小孩向汇流Bi/2。 然后看剩下的糖够不够补完那些不够的 SGU 326 Perspective 所有队伍打几场比赛，每场比赛都有一支队伍赢和另一支队伍输掉。所有队伍被分成几个小组，一些比赛是在同一小组队伍中进行的较量，而另一些比赛是在小组与小组的较量。给出现在球队的分数和你们组中所有队伍参加的比赛数目，和每个队伍两两之间剩下的比赛数量。确定球队是否能在小组赛中得第一。 Solution 比较明显的最大流模型了。 分为2层为比赛和球队。 源向比赛流场数那么多的流量。 比赛向2只参赛队伍各流比赛场数那么多的流量。 队伍向汇流第一支队伍的最大胜场数减去自己当前胜场数的流量。 最后的流量为总比赛数则可构造出。 Extension：比赛为积分制呢？ Poj 1149 pigs 题目大意 Mirko养着一些猪 猪关在一些猪圈里面 猪圈是锁着的 他自己没有钥匙（汗） 只有要来买猪的顾客才有钥匙 顾客依次来 每个顾客会用他的钥匙打开一些猪圈 买走一些猪 然后锁上 在锁上之前 Mirko有机会重新分配这几个已打开猪圈的猪 现在给出一开始每个猪圈的猪数 每个顾客所有的钥匙和要买走的猪数 问Mirko最多能卖掉几头猪 数据规模 猪圈数n=1000 顾客数m=100 每个猪圈的猪数不超过1000 假设猪圈容量无限 样例 3 3 3 1 10 2 1 2 2 2 1 3 3 1 2 6 3个猪圈分别有3，1，10头猪 第一个顾客有1，2猪圈的钥匙要买2头 第二个顾客有1，3猪圈的钥匙要买3头 第三个顾客有2猪圈的钥匙要买6头 上面的样例可以构造出下面的模型, （图中凡是没有标数字的边，容量都是 +∞）： 三个顾客，就有三轮交易，每一轮分别都有 3 个猪圈和 1 个顾客的节点。 1） 三个顾客，就有三轮交易，