any idea? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

any idea?

any idea?# JobHunting - 待字闺中

a*y2012-08-20 07:08

1 楼

There is a set of 9 students and 3 schools Every school can be alloted at
max 3 students .Every school and student has its coordinates .Now we have to
allot student in such a way that the sum of distance from all the student
to the school should be minimum.
穷举太费时了
而且第k次应该不是建立在min（k-1 ）次的，想想有可能学校之间距离很长，有点学生
离第一个比其他的近一点，但是其他的学生可能离这两个学校更远，

f*e2012-08-20 07:08

2 楼

weighted最大流 or minimum cost flow。每个学校capacity为3，每个学生入流为1。
可能是这个方向吧？
建立一个bipartite图，左边是源点s，入流是学生数目，与每个学生有一条连线，
capacity是1，然后是学生，然后是学校，学校与sink t的edge capacity是3。
http://www.cs.tau.ac.il/~zwick/grad-algo-06/min-cost-flow.pdf

to

【在 a*******y 的大作中提到】

: There is a set of 9 students and 3 schools Every school can be alloted at
: max 3 students .Every school and student has its coordinates .Now we have to
: allot student in such a way that the sum of distance from all the student
: to the school should be minimum.
: 穷举太费时了
: 而且第k次应该不是建立在min（k-1 ）次的，想想有可能学校之间距离很长，有点学生
: 离第一个比其他的近一点，但是其他的学生可能离这两个学校更远，

j*o2012-08-20 07:08

3 楼

min cost flow 是一个SOURCE,一个DESTINATION吧？
这个图是说学生都是源点，那共有9个源点？
我没搞清楚这个BIPARTITE GRAPH怎么画。。
REQ DETAIL
THX

【在 f*****e 的大作中提到】

: weighted最大流 or minimum cost flow。每个学校capacity为3，每个学生入流为1。
: 可能是这个方向吧？
: 建立一个bipartite图，左边是源点s，入流是学生数目，与每个学生有一条连线，
: capacity是1，然后是学生，然后是学校，学校与sink t的edge capacity是3。
: http://www.cs.tau.ac.il/~zwick/grad-algo-06/min-cost-flow.pdf
:
: to

g*y2012-08-20 07:08

4 楼

DP? C[i][x][y][z]: the minimum distance sum when there are i students, and
each school can get x, y and z students. (i = x+ y+z)

l*h2012-08-20 07:08

5 楼

分几步走
1，9个学生平均分配到3个学校（这步也可以优化一下提高效率，也可以随机分），假
设学校编号为1，2，3。
2，计算是否有学校1的一学生移动到学校2，学校2的一个学生转到学校3，和学校3的一
个学生转到学校1，其总的距离增加量为负。重复直到不能再减少总距离。这步简计为1
一2一3。
3，类似于步骤2，做3一2一1。
4，重复步骤2和3，直到不能再移。