–author: Answeror
—title: [PKU][3204][Ikki's Story I - Road Reconstruction]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3204
—-date: 2009-08-13
-problem: 求最小割中有多少边扩容后能使最大流增大(不能同时扩容).
solution: 求最大流, 对残留网络两边dfs标号1和2, 找原图中边两端标号分别是1和2的边数. 或者枚举满流边, 扩容重做最大流.
—-code: http://docs.google.com/View?id=dgtsspfh_43qjz3rmhr
Helanic Abyss
I am the answer.
[PKU][POJ][3204][Ikki's Story I - Road Reconstruction]
[PKU][POJ][2125][Destroying The Graph]
–author: Answeror
—title: [PKU][2125][Destroying The Graph]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2125
—-date: 2009-08-13
-problem: 一个有向图, 可以删除一个点的所有入边, 代价a[u], 可以删除一个点的所有出边, 代价b[u], 求删除所有边的最小代价.
solution: 有向图上的最小点覆盖集, 转化成最小割.
—-code: http://docs.google.com/View?id=dgtsspfh_42cz3twscm
[PKU][POJ][3498][March of the Penguins]
–author: Answeror
—title: [PKU][3498][March of the Penguins]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3498
—-date: 2009-08-13
-problem: 二维整数坐标系上有n块浮冰, 每块上有若干只企鹅, 企鹅每次最多跳d个单位远, 浮冰有耐久度, 每有一只企鹅从它上面起跳, 浮冰的耐久-1, 减到0浮冰就消失, 现在企鹅要跳到同一块浮冰上, 问企鹅可能最终聚集在哪些浮冰上.
solution: 拆点建图, 枚举汇点.
—-code: http://docs.google.com/View?id=dgtsspfh_41ffwftwdz
[PKI][POJ][3308][Paratroopers]
–author: Answeror
—title: [PKI][3308][Paratroopers]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3308
—-date: 2009-08-13
-problem: 整点坐标系上有n个伞兵, 现在要在坐标轴上的若干点架设大炮, 发射方向平行于另一轴, 炮线上所有伞兵均消灭, 每个点架设大炮的费用已知, 问最少花费多少消灭所有伞兵. 横纵坐标轴范围均<=50.
solution: 二分图带权匹配, 或用最大流算法求最小割.
—-code: http://docs.google.com/View?id=dgtsspfh_40dh6mq3c7
[PKU][POJ][3469][Dual Core CPU]
–author: Answeror
—title: [PKU][3469][Dual Core CPU]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3469
—-date: 2009-08-13
-problem: 一系列任务要在双核CPU上完成, 每个任务有各自在每个CPU上的基本花费, 不同任务之间若不在同一个CPU上要有额外花费, 求分配方案使得总花费最小, 任务数n<=20000, 额外花费种树m<=200000.
solution: 建图求最小边割.
—-code: http://docs.google.com/View?id=dgtsspfh_39d5fkz4ch
{PKU}{3189}{Steady Cow Assignment}
-problem: 有n(< =1000)头牛, b(<=20)个牛棚, 每个牛棚有自己的容量, 每头牛按喜好程度为b个牛棚打上不同的分数, 现在分配牛去牛棚, 设第i头牛对分配的牛棚的喜好值为rank[i], 问在不挤爆牛棚的前提下, 怎样分配, 使得max{rank[i]}-min{rank[j]}最小.
solution: 首尾指针枚举答案, 最大流, 继续增广路
----link: http://poj.org/problem?id=3189
----code: http://goo.gl/AkAF
[PKU][POJ][3463][Sightseeing]
–author: Answeror
—title: [PKU][3463][Sightseeing]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3463
—-date: 2009-07-17
-problem: 求最短路个数以及比最短路长1的个数.
solution: 二维状态的Dijkstra.
—-code: http://docs.google.com/View?id=dgtsspfh_37c6nkptf2
[PKU][POJ][2699][The Maximum Number of Strong Kings]
–author: Answeror
—title: [PKU][2699][The Maximum Number of Strong Kings]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2699
—-date: 2009-08-10
-problem: n个人比赛, 每人都要和其余的比一场, 打败一个人得一分, 如果一个人打败了所有比自己分数高的人, 或者他本身就是分数最高的, 那么他就是Strong King, 可能有多个Strong King, 现在按非降的顺序给你每个人的得分, 问Strong King最多能有几个. n<=10.
solution: 枚举Strong King个数, 加一坨点建图, 最大流判可行性.
—-code: http://docs.google.com/View?id=dgtsspfh_36dckn9sdf
[PKU][POJ][2455][Secret Milking Machine]
–author: Answeror
—title: [PKU][2455][Secret Milking Machine]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2455
—-date: 2009-08-10
-problem: 一个n个顶点的无向图, 从1出发去n, 要求走t条不同的路径, 两条路径不同当且仅当它们没有共同的边, 现保证存在t条路径, 求t条路径上最长的边的最小值是多少.
solution: 二分答案, 加一个源点建图, 求最大流.
—-code: http://docs.google.com/View?id=dgtsspfh_35gs7hzjfx
[PKU][POJ][2112][Optimal Milking]
—title: [PKU][2112][Optimal Milking]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2112
—-date: 2009-08-08
-problem: k个挤奶机, c头奶牛, 每个挤奶机最多供应m头奶牛, 奶牛, 挤奶机之间都有一定距离, 用邻接矩阵表示, 求一种分配方案, 使得走得最远的奶牛走过的距离最小化. 输出此距离.
solution: 二分答案, 添加源点汇点建图, 求最大流是否为c.
—-code: http://docs.google.com/View?id=dgtsspfh_34f457vvd5