a*******y
发帖数: 1040 | 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*****e
发帖数: 2992 | 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*****o
发帖数: 394 | 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****y
发帖数: 240 | 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****h
发帖数: 272 | 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，直到不能再移。 |
