[POJ 3565] 最小费用流 利用重要性质

【题目大意】:给定2*N个点的坐标,让你用前N个点和后N个点一一配对,使得相连的边没有相交的。

【算法分析】:首先有一个性质必须知道,那就是最短的配对,必然是没有相交的。于是我们就可以构建二分图,求最小权匹配。(用最小费用流求解)

【code】

#include

加入对话

2条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注