[POJ 3565] 最小费用流 利用重要性质 发布者:edward_mj 1月 2, 2010 [POJ 3565] 最小费用流 利用重要性质有2条评论 【题目大意】:给定2*N个点的坐标,让你用前N个点和后N个点一一配对,使得相连的边没有相交的。 【算法分析】:首先有一个性质必须知道,那就是最短的配对,必然是没有相交的。于是我们就可以构建二分图,求最小权匹配。(用最小费用流求解) 【code】 #include 文章导航 上一篇文章 上一篇文章: [HDOJ 1914] 稳定婚姻系统下一篇文章 下一篇文章: [POJ1062 昂贵的聘礼] 最短路 加入对话 2条评论 很ym 很有拜师的冲动。。。表示图论一点不懂 回复 回复sulipol:= =这么囧。。。 回复 留下评论 取消回复您的电子邮箱地址不会被公开。 必填项已用*标注评论 * 显示名称 电子邮箱地址 网站地址 在此浏览器中保存我的显示名称、邮箱地址和网站地址,以便下次评论时使用。 通过邮件通知我后续评论 通过邮件通知我有新文章 Δ
很ym 很有拜师的冲动。。。表示图论一点不懂
回复sulipol:= =这么囧。。。