team2012-D1-sol-0004

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

=== 解题思路 ===
用线性规划来解决:

求 max r1+r2+r3+r4

限制: 

r1+r2 <= dis(p1,p2)

r1+r3 <= dis(p1,p2)

r1+r4 <= dis(p1,p4)

r2+r3 <= dis(p2,p3)

r2+r4 <= dis(p2,p4)

r3+r4 <= dis(p3,p4)

还可以进一步发现其实只要很简单的取几个 max ...

解题思路

用线性规划来解决:

求 max r1+r2+r3+r4

限制:

r1+r2 <= dis(p1,p2)

r1+r3 <= dis(p1,p2)

r1+r4 <= dis(p1,p4)

r2+r3 <= dis(p2,p3)

r2+r4 <= dis(p2,p4)

r3+r4 <= dis(p3,p4)

还可以进一步发现其实只要很简单的取几个 max ...