GG热腾腾的电面

lll_2013 发表于 2016-9-9 02:53
我不知道我有没有理解错题意，person[n]，表示在人在coordinate上坐标，bike[n]表示 bike在coordinate上坐 ...

图是2D的，
1D 为什么从 做到右而不从右到左 ， 两种方向得到的结果应该不一样。

fatalme 发表于 2016-9-9 00:57
不是整数规划，至少minimum weight perfect matching

补充内容 (2016-9-9 01:33):

可以详细说一下么？

这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是每个车的点Bike,最左边是源点s,最右边是汇点t.通过边容量限制每个人只能有一辆车,每辆车只能被一个拥有(s到每个People容量为1,每个Bike到t的容量为1).中间边的费用就是车的距离.然后用费用流算法搞搞就能出最优结果.

差不多，同意楼上的。

dydcfg 发表于 2016-9-9 05:34
这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是 ...

费用流算法是啥？有具体链接吗

二分图匹配

wtcupup 发表于 2016-9-9 09:08
费用流算法是啥？有具体链接吗

https://en.wikipedia.org/wiki/Maximum_flow_problem

dydcfg 发表于 2016-9-9 05:34
这应该是个最小费用最大流问题吧...电面考这个确实有点=。=
搞一个二分图,左边是每个人的点People,右边是 ...

如何控制变容量限制每人只有一辆车呢？

wtcupup 发表于 2016-9-9 09:08
费用流算法是啥？有具体链接吗

http://courses.csail.mit.edu/6.8 ... -minCostFlowAlg.pdf

这里有份讲义~

xihaokai1 发表于 2016-9-9 09:23
如何控制变容量限制每人只有一辆车呢？

假设源点是s,然后每个人的点是p1,p2...pn.
建图的时候capacity[pi]=1,这样确保每个人最多只有1的流量汇入相当于只能选一辆车.