–author: Answeror
—title: [PKU][1149][PIGS]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1149
—-date: 2009-08-21
-problem: 有m个猪圈, n个客户, 猪圈钥匙在客户手里(老板脑残了?), n个客户按编号顺序一个一个来, 每个各户有各自的钥匙数和需求量, 来一个就把他拥有的所有钥匙对应的猪圈打开, 选择其中一些卖给客户, 不要求一定满足客户的需求量, 在这期间, 老板也可以在开着的猪圈间转移任意数量的猪, 客户走了门就锁上, 问最多卖多少头猪.
solution: 可以以猪圈和客户为顶点, 也可以只以客户为顶点建图, 求最大流.
—-code: http://docs.google.com/View?id=dgtsspfh_53cgd2qk7n
Helanic Abyss
I am the answer.
[PKU][POJ][1149][PIGS]
[PKU][POJ][2400][Supervisor, Supervisee]
–author: Answeror
—title: [PKU][2400][Supervisor, Supervisee]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2400
—-date: 2009-08-20
-problem: n个雇主n个员工, 每个雇主对每个员工有不同的喜好值0~n-1, 0表示最喜欢, 每个员工对每个雇主也有喜好值, 定义同前, 问怎样分配使得总喜好值对2n个人取平均的值最小, 按字典序输出所有方案.
solution: KM算法解二分图最小权匹配
—-code: http://docs.google.com/View?id=dgtsspfh_52dnjzc6gr
[TJU][TOJ][3335][Phalanx]
–author: Answeror
—title: [TJU][3335][Phalanx]
—-link: http://acm.tju.edu.cn/toj/showp3335.html
—-date: 2009-08-20
-problem: 给你一个n(<=1000)阶的字符方阵, 求沿副对角线对称的最大子阵. 时限5000MS.
solution: 枚举副对角线, DP.
—-code: http://docs.google.com/View?id=dgtsspfh_51gbtgvxd6
[PKU][POJ][2195][Going Home]
–author: Answeror
—title: [PKU][2195][Going Home]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2195
—-date: 2009-08-19
-problem: 一个字符方阵, 其中’H'代表房子, ‘m’代表人, 两者数量相同, 两地间距离定义为曼哈顿距离, 每个房子只能容纳一个人, 最小路程总和为多少.
solution: KM算法解二分图最小权匹配
—-code: http://docs.google.com/View?id=dgtsspfh_50grdcvhgk
[PKU][POJ][1077][Eight]
–author: Answeror
—title: [PKU][1077][Eight]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1077
—-date: 2009-08-19
-problem: 八数码问题
solution: A Star, 双向BFS, 随便选一个, 状态表示可以用字符串hash, 也可以用排列数.
—-code: http://docs.google.com/View?id=dgtsspfh_49djt545ng
[PKU][POJ][1486][Sorting Slides]
–author: Answeror
—title: [PKU][1486][Sorting Slides]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1486
—-date: 2009-08-18
-problem: 求二分图的必须边.
solution: Hungary求最大匹配, 然后依次删除匹配边, 再找增广路, 若不能找到增广路则是必须边.
—-code: http://docs.google.com/View?id=dgtsspfh_48dwqv74hr
{HDU}{2389}{Rain on your Parade}
-problem: 有m(< =3000)个人, n(<=3000)把伞分布在二维整数坐标系上, t分钟后下雨, 每个人有各自的移动速度, 不允许合用一把伞, 每个人按最短路移动, 问最多能有多少人不淋雨. 时限5000MS, 空间65535K. solution: Hopcroft-Karp算法求解二分图匹配. --source: HDU 2008-10 Public Contest ----link: http://acm.hdu.edu.cn/showproblem.php?pid=2389 ----code: http://goo.gl/jsJz
[PKU][POJ][2987][Firing]
–author: Answeror
—title: [PKU][2987][Firing]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2987
—-date: 2009-08-17
-problem: 公司要炒一些员工的鱿鱼, 若A被炒了, 那A的所有下属也会跟着被炒, 下属关系具有传递性, 且可能构成环, 即A是B的下属, B又间接是A的下属, 炒掉每个人公司会得到一笔收益, 收益可能为负, 问在收益最大的前提下, 最少要炒掉哪些人, 以及最大收益是多少.
solution: 建图求最小割, 从源点对残留网络做DFS, 得到最小的点集合.
—-code: http://docs.google.com/View?id=dgtsspfh_46htsnc2dw
[HDU][HOJ][2929][Bigger is Better]
–author: Answeror
—title: [HDU][2929][Bigger is Better]
—-link: http://acm.hdu.edu.cn/showproblem.php?pid=2929
—-date: 2009-08-17
-problem: 有n根火柴, 要求组成一个七段数码组成的十进制数, 要求此数是m的倍数, 问此数最大为多少? (火柴可以不用完)
solution: 以火柴数和对m取模的值为状态DP
—-code: http://docs.google.com/View?id=dgtsspfh_45g3trbpgk
[PKU][POJ][3514][The Writers' Club]
–author: Answeror
—title: [PKU][3514][The Writers' Club]
—-link: http://acm.pku.edu.cn/JudgeOnline/problem?id=3514
—-date: 2009-08-14
-problem: 有n(<=100000)个人, 其中m(<=100)个是作者, 现在告诉你哪些人喜欢哪个作者, 喜欢有传递性, 若A喜欢B, B也喜欢C, 则A间接喜欢C, 若A本来就喜欢C或者A就是C则不能说A间接喜欢C, 问每个作者被哪些人间接喜欢. (作者按字典序输出在行首, 每个作者的间接fans也按字典序输出在同一行, 所有名字不超过16字符, 名字间有任意空格)
solution: 传递闭包
—-code: http://docs.google.com/View?id=dgtsspfh_44d3d9qtgx