c*********t
发帖数: 1861 | 1 Solution 见楼底。。。
这次N 个 WSN 因为已经脑残了，所以相约劳动节去绣花 。。。好了，废话就不说了，大家帮我想这个题:
不同的 WSN 绣不同的款式需要的时间不一样。如果我们把 WSN # i 绣 j 款式需要的时间记做 T(i,j), 那么，T(i,j)组成了一个 N by N 的正整数矩阵。
现在要找出一个方案，让 WSN 总体用最短的时间把所有款式都绣出来
例1 [不可以每行都选时间最短的]：考虑如下3x3的矩阵：
1 2 2
2 1 2
2 2 9 ==> choose (2,2,2) = 6
例2：[有时候还必须 include 时间最长的]: 考虑如下3x3的矩阵：
1 4 4
4 1 4
4 4 5 ==> choose (1,1,5) = 7
当然，Naively, 可以把 N! 种可能性都试一遍。但是 N (max N = 75) 很大的时候，这个方法无法满足要求。是否有更聪明的算法呢？
原题链接：
http://code.google.com/codejam/contest/dashboard?c=32014#s=p3 |
i*********n
发帖数: 219 | |
c*********t
发帖数: 1861 | 3 哈，这张狠威风，偶笑纳了。。。
【在 i*********n 的大作中提到】
: 这张图片是送给你的
: 以表彰你的丰功伟绩
|
i*********n
发帖数: 219 | |
j*******a
发帖数: 2681 | 5 咱不出这样的题目成么，猫从来做不出的。。。
抗议~
我为什么，因为我还没有想出答案。好了，废话就不说了，大家帮我想这个题:
果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么，A(i,j)组成了一个 N by N
的正整数矩阵。
的）
。。。
【在 c*********t 的大作中提到】
: 哈，这张狠威风，偶笑纳了。。。
|
n********6
发帖数: 1511 | 6 谢版兔隆恩。
【在 i*********n 的大作中提到】
: 谢版主兔恩
|
s*******u
发帖数: 5796 | 7 motel没有这样做生意的啊！不同顾客入住房价不一样，还想不想干了？！告你
discrimination！疯兔你还是换个比喻好了。这样太confusing~ |
h********r
发帖数: 3291 | 8 我要是wsn，要么住霸王店，要么搭帐篷。住个店都怎么麻烦，你说以后还有哪个ppmm
会跟你出去玩？真是脑子彻底进水了。
(这个问题应该是np－complete，还是不要最便宜，只要差不多便宜就可以了。用随机
mutation＋tunneling)
我为什么，因为我还没有想出答案。好了，废话就不说了，大家帮我想这个题:
果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么，A(i,j)组成了一个 N by N
的正整数矩阵。
的）
。。。
【在 c*********t 的大作中提到】
: 哈，这张狠威风，偶笑纳了。。。
|
c*********t
发帖数: 1861 | 9 如你所愿，题目已做改动。
我土，什么叫做 tunneling 啊？ Is it something like aborting search
pre-maturely?
ppmm
N
【在 h********r 的大作中提到】
: 我要是wsn，要么住霸王店，要么搭帐篷。住个店都怎么麻烦，你说以后还有哪个ppmm
: 会跟你出去玩？真是脑子彻底进水了。
: (这个问题应该是np－complete，还是不要最便宜，只要差不多便宜就可以了。用随机
: mutation＋tunneling)
:
: 我为什么，因为我还没有想出答案。好了，废话就不说了，大家帮我想这个题:
: 果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么，A(i,j)组成了一个 N by N
: 的正整数矩阵。
: 的）
: 。。。
|
A*********t
发帖数: 7481 | 10 我觉得这个版都进水了。
。。不要问我为什么，因为我还没有想出答案。好了，废话就不说了，大家帮我想这个
题:
们把 WSN No.i 搞定 MM No.j 需要的时间记做 T(i,j), 那么，T(i,j)组成了一个 N
by N 的正整数矩阵。
不必要的流血事件，不可以让两个 WSN 去泡同一个MM。。。
【在 c*********t 的大作中提到】
: 如你所愿，题目已做改动。
: 我土，什么叫做 tunneling 啊？ Is it something like aborting search
: pre-maturely?
:
: ppmm
: N
|
D********e
发帖数: 475 | 11 I guess google wants an exact algorithm for this problem.
ppmm
N
【在 h********r 的大作中提到】
: 我要是wsn，要么住霸王店，要么搭帐篷。住个店都怎么麻烦，你说以后还有哪个ppmm
: 会跟你出去玩？真是脑子彻底进水了。
: (这个问题应该是np－complete，还是不要最便宜，只要差不多便宜就可以了。用随机
: mutation＋tunneling)
:
: 我为什么，因为我还没有想出答案。好了，废话就不说了，大家帮我想这个题:
: 果我们把 WSN No.i 住房间 #j 的价格记做 A(i,j), 那么，A(i,j)组成了一个 N by N
: 的正整数矩阵。
: 的）
: 。。。
|
i*********n
发帖数: 219 | |
c*********t
发帖数: 1861 | 13 真是踏破旅游鞋。。。昨天无意中搜到一个 Hungarian 算法，O(N^4)把问题解决了。
思想方法是先找到（冲突的）局部最优，然后逐步放松（找次优）调整消除冲突。不过
这个算法比较 non-intuitive. 有兴趣的群众可以参考：
http://en.wikipedia.org/wiki/Hungarian_algorithm
真不知道那些得满分的疯子怎么会在2小时内记得这些东西。。。
，大家帮我想这个题:
的时间记做 T(i,j), 那么，T(i,j)组成了一个 N by N 的正整数矩阵。
【在 c*********t 的大作中提到】
: 如你所愿，题目已做改动。
: 我土，什么叫做 tunneling 啊？ Is it something like aborting search
: pre-maturely?
:
: ppmm
: N
|
D********e
发帖数: 475 | 14 Just realized this is maximum weighted bipartite matching. Should be easily
solvable with augmenting path algorithm.
【在 c*********t 的大作中提到】
: 真是踏破旅游鞋。。。昨天无意中搜到一个 Hungarian 算法，O(N^4)把问题解决了。
: 思想方法是先找到（冲突的）局部最优，然后逐步放松（找次优）调整消除冲突。不过
: 这个算法比较 non-intuitive. 有兴趣的群众可以参考：
: http://en.wikipedia.org/wiki/Hungarian_algorithm
: 真不知道那些得满分的疯子怎么会在2小时内记得这些东西。。。
:
: ，大家帮我想这个题:
: 的时间记做 T(i,j), 那么，T(i,j)组成了一个 N by N 的正整数矩阵。
|
