G家关于图的一道题 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>JobHunting - 待字闺中

G家关于图的一道题

G家关于图的一道题# JobHunting - 待字闺中

f*a2015-03-19 07:03

1 楼

说是一次party完以后，有的人负责酒水费用有的人负责汽油费用有的人负责。。这样
形成一个有向图的结构，A欠B多少钱，B欠C多少钱，C可能欠A、B分别多少钱，问怎么
reduce/combine到最后形成一些pairs，比如A欠B 20，C欠A20，reduce到最后只需要C
给B20块就行。这个pairs表达的transactions做到最小。
有人说用二分图最大权匹配，还是没有懂到怎么做。。。

d*c2015-03-19 07:03

2 楼

我觉得可不可以这样：计算出一个人的净收入，比如要C要付给A 20，要给B 10，自
己能得到 10，那么净收入就是 -20，也就是要付出20. 然后得到一个array, sort一
下，跟做two sum一样从两天扫，付出的多的给得到的多的。
不知道对不对，还请大神来解答。

I*y2015-03-19 07:03

3 楼

你这个算法是不对的。比如一个数列是1, 2, ..., n, 另一面是2, 3, ..., n - 1, n
+ 1
你的算法会比最优解多出将近一倍
这个问题实际上是np hard的，从partition归约，n个数放左面，两个结点放右边，每
个的权分别是左面和的一半。partition问题有解的话，这个问题的解是n，否则这个问
题的解是n+1。所以此题没有多项式时间解。应该有伪多项式时间的DP解法

【在 d*****c 的大作中提到】