Uvalive 4043 Ants —— 二分图最大权匹配 KM算法

news/2024/7/24 10:24:56 标签: 数据结构与算法

题目链接:https://vjudge.net/problem/UVALive-4043

 

 

 

题意:

给出n个白点和n个黑点的坐标, 要求用n条不相交的线段把他们连接起来,其中每条线段恰好连接一个白点和黑点,每个点恰好连接到一条线段。输出每个白点与其相连的黑点的编号。

 

 

题解:

1.首先随便配对。然后,如果存在两对黑白点的线段是相交的,那么就交换他们的配对对象。交换之后重新形成的线段就不会相交了(画画图就可看出)。而且可以推出一个结论:交换之后,两条线段之和必定变小。这是因为根据三角形定理:

2.有了上述结论之后,我们就能推出:对于当前配对,如果线段总和还能继续变小,那么就可能存在交叉;但如果线段总和不能再小了,即已经达到最小,那么就不存在交叉了。所以我们只需要求最大权匹配(边权取反),就能满足要求了。

 

 

代码如下:

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 typedef long long LL;
  4 const int INF = 2e9;
  5 const LL LNF = 9e18;
  6 const double EPS = 1e-8;
  7 const int MOD = 1e9+7;
  8 const int MAXN = 1e2+10;
  9 
 10 struct Node{
 11     double x, y;
 12 }black[MAXN], white[MAXN];
 13 
 14 int nx, ny;
 15 double  g[MAXN][MAXN];
 16 int linker[MAXN];
 17 double lx[MAXN], ly[MAXN], slack[MAXN];
 18 bool visx[MAXN], visy[MAXN];
 19 
 20 bool DFS(int x)
 21 {
 22     visx[x] = true;
 23     for(int y = 1; y<=ny; y++)
 24     {
 25         if(visy[y]) continue;
 26         double tmp = lx[x] + ly[y] - g[x][y];
 27         if(tmp<EPS)
 28         {
 29             visy[y] = true;
 30             if(linker[y]==-1 || DFS(linker[y]))
 31             {
 32                 linker[y] = x;
 33                 return true;
 34             }
 35         }
 36         else
 37             slack[y] = min(slack[y], tmp);
 38     }
 39     return false;
 40 }
 41 
 42 void KM()
 43 {
 44     memset(linker, -1, sizeof(linker));
 45     memset(ly, 0, sizeof(ly));
 46     for(int i = 1; i<=nx; i++)
 47     {
 48         lx[i] = -INF;
 49         for(int j = 1; j<=ny; j++)
 50             lx[i] = max(lx[i], g[i][j]);
 51     }
 52 
 53     for(int x = 1; x<=nx; x++)
 54     {
 55         for(int i = 1; i<=ny; i++)
 56             slack[i] = INF;
 57         while(true)
 58         {
 59             memset(visx, 0, sizeof(visx));
 60             memset(visy, 0, sizeof(visy));
 61 
 62             if(DFS(x)) break;
 63             double d = INF;
 64             for(int i = 1; i<=ny; i++)
 65                 if(!visy[i])
 66                     d = min(d, slack[i]);
 67 
 68             for(int i = 1; i<=nx; i++)
 69                 if(visx[i])
 70                     lx[i] -= d;
 71             for(int i = 1; i<=ny; i++)
 72             {
 73                 if(visy[i]) ly[i] += d;
 74                 else slack[i] -= d;
 75             }
 76         }
 77     }
 78 }
 79 
 80 int main()
 81 {
 82     int kase = 0, n;
 83     while(scanf("%d", &n) != EOF)
 84     {
 85         if(kase++) printf("\n");
 86 
 87         nx = ny = n;
 88         for (int i = 1; i <= n; i++)
 89             scanf("%lf%lf", &black[i].x, &black[i].y);
 90         for (int i = 1; i <= n; i++)
 91             scanf("%lf%lf", &white[i].x, &white[i].y);
 92 
 93         for (int i = 1; i <= n; i++)
 94         {
 95             double x1 = white[i].x, y1 = white[i].y;
 96             for (int j = 1; j <= n; j++)
 97             {
 98                 double x2 = black[j].x, y2 = black[j].y;
 99                 g[i][j] = -sqrt( (x1-x2)*(x1 - x2) + (y1-y2)*(y1-y2) );
100             }
101         }
102 
103         KM();
104         for(int i = 1; i<=n; i++)
105             printf("%d\n", linker[i]);
106     }
107 }
View Code

 

转载于:https://www.cnblogs.com/DOLFAMINGO/p/7832243.html


http://www.niftyadmin.cn/n/1109881.html

相关文章

清华紫光笔记本和PC电脑预装LINUX操作平台(转)

清华紫光笔记本和PC电脑预装LINUX操作平台(转)[more]来源&#xff1a;京华时报 记者&#xff1a;熊海燕昨天&#xff0c;紫光计算机系统事业部总经理姬浩向记者透露&#xff0c;目前&#xff0c;清华紫光新上市的笔记本和PC电脑全部预装了正版软件&#xff0c;但紫光却绕道微软…

课后作业一

问题&#xff1a; &#xff08;1&#xff09;回想一下你初入大学时对计算机专业的畅想 当初是如何做出选择计算机专业的决定的&#xff1f;从小就喜欢计算机&#xff0c;所以报的计算机你认为过去两年中接触到的课程是否符合你对计算机专业的期待&#xff0c;为什么&#xff1f…

Python学习(十) —— 常用模块

一、collections模块 在内置数据类型&#xff08;dict、list、set、tuple&#xff09;的基础上&#xff0c;collections模块还提供了几个额外的数据类型&#xff1a;Counter、deque、defaultdict、namedtuple和OrderedDict等。 1.namedtuple&#xff1a;生成可以使用名字来访问…

layoutInflater参数解析与源码分析

关于LayoutInflater方法&#xff0c;无论是在listview的适配器中&#xff0c;还是在动态添加view的时候&#xff0c;都会出现它的身影&#xff0c;最开始我在看《第一行代码》时&#xff0c;不知道这个方法实际的参数到底指的是什么意思&#xff0c;后来看了一些博客以及查看了…

PHP旧系统基于命名空间重构经验

命名空间其实只是一个形式&#xff0c;最终目的是重构代码&#xff0c;但这个过程想要一蹴而就是不可能的。 一开始给了一个伪命题&#xff1a;基于ThinkPHP的重构&#xff08;不要问为什么&#xff09;。经过一段的实践&#xff0c;发现这是一个大错特错的思维方式&#xff0c…

近9成盗版Office用户称愿投奔开源(转)

近9成盗版Office用户称愿投奔开源(转)[more]2006年04月28日 11:47 eNet硅谷动力 【eNet硅谷动力消息】据国外媒体报道&#xff0c;微软公司模仿"Windows正版增值计划"推出"Office正版增值计划"&#xff0c;市场反映如何&#xff1f;最近&#xff0c;iTWire…

常用安卓模拟器都有哪些?适用范围?----------持续更新(欢迎各位园友补充,谢谢)...

-【Genymotion】 适合人群&#xff1a;开发者、测试人员、有一定配置基础&#xff0c;配合VirtualBox运行&#xff0c;流畅兼容较好&#xff0c;需要一定配置经验&#xff0c;英文界面。   优 点&#xff1a;安卓版本更新较快 缺 点&#xff1a;比较好的技术方面的…

Android学习笔记(十九)——内容提供器

//此系列博文是《第一行Android代码》的学习笔记&#xff0c;如有错漏&#xff0c;欢迎指正&#xff01; 内容提供器&#xff08;Content Provider&#xff09;主要用于在不同的应用程序之间实现数据共享的功能&#xff0c;它提供了一套完整的机制&#xff0c;允许一个程序访问…