Young naturalist Bill studies ants in school. His ants feed on plant-louses that live on apple trees. Each ant colony needs its own apple tree to feed itself.
Bill has a map with coordinates of n <tex2html_verbatim_mark>ant colonies and n <tex2html_verbatim_mark>apple trees. He knows that ants travel from their colony to their feeding places and back using chemically tagged routes. The routes cannot intersect each other or ants will get confused and get to the wrong colony or tree, thus spurring a war between colonies.
Bill would like to connect each ant colony to a single apple tree so that all n <tex2html_verbatim_mark>routes are non-intersecting straight lines. In this problem such connection is always possible. Your task is to write a program that finds such connection.
On this picture ant colonies are denoted by empty circles and apple trees are denoted by filled circles. One possible connection is denoted by lines.
Input
Input has several dataset. The first line of each dataset contains a single integer number n <tex2html_verbatim_mark>(1n100) <tex2html_verbatim_mark>-- the number of ant colonies and apple trees. It is followed by n <tex2html_verbatim_mark>lines describing n <tex2html_verbatim_mark>ant colonies, followed byn <tex2html_verbatim_mark>lines describing n <tex2html_verbatim_mark>apple trees. Each ant colony and apple tree is described by a pair of integer coordinates x <tex2html_verbatim_mark>and y <tex2html_verbatim_mark>(- 10000x, y10000) <tex2html_verbatim_mark>on a Cartesian plane. All ant colonies and apple trees occupy distinct points on a plane. No three points are on the same line.
Output
For each dataset, write to the output file n <tex2html_verbatim_mark>lines with one integer number on each line. The number written on i <tex2html_verbatim_mark>-th line denotes the number (from 1 to n <tex2html_verbatim_mark>) of the apple tree that is connected to the i i<tex2html_verbatim_mark>-th ant colony. Print a blank line between datasets.
Sample Input
5 -42 58 44 86 7 28 99 34 -13 -59 -47 -44 86 74 68 -75 -68 60 99 -60
Sample Output
4 2 1 5 3
#include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const int maxn = 100 + 10; const double INF = 1e30; int n; double W[maxn][maxn]; double Lx[maxn], Ly[maxn]; // 顶标 int left[maxn]; // left[i]为右边第i个点的匹配点编号 bool S[maxn], T[maxn]; // S[i]和T[i]为左/右第i个点是否已标记 bool eq(double a, double b) { return fabs(a-b) < 1e-9; } bool match(int i){ S[i] = true; for(int j = 1; j <= n; j++) if (eq(Lx[i]+Ly[j], W[i][j]) && !T[j]){ T[j] = true; if (!left[j] || match(left[j])){ left[j] = i; return true; } } return false; } void update(){ double a = INF; for(int i = 1; i <= n; i++) if(S[i]) for(int j = 1; j <= n; j++) if(!T[j]) a = min(a, Lx[i]+Ly[j] - W[i][j]); for(int i = 1; i <= n; i++) { if(S[i]) Lx[i] -= a; if(T[i]) Ly[i] += a; } } void KM() { for(int i = 1; i <= n; i++) { left[i] = Lx[i] = Ly[i] = 0; for(int j = 1; j <= n; j++) Lx[i] = max(Lx[i], W[i][j]); } for(int i = 1; i <= n; i++) { for(;;) { for(int j = 1; j <= n; j++) S[j] = T[j] = 0; if(match(i)) break; else update(); } } } int main(){ int kase = 0; while(scanf("%d", &n) == 1) { if(++kase > 1) printf("\n"); int x1[maxn], y1[maxn], x2[maxn], y2[maxn]; for(int i = 1; i <= n; i++) scanf("%d%d", &x1[i], &y1[i]); for(int i = 1; i <= n; i++) scanf("%d%d", &x2[i], &y2[i]); for(int i = 1; i <= n; i++) // ant colony for(int j = 1; j <= n; j++) //存成负数找最大值,相当于找最小值 W[j][i] = -sqrt((double)(x1[i]-x2[j])*(x1[i]-x2[j]) + (double)(y1[i]-y2[j])*(y1[i]-y2[j])); KM(); // 最大权匹配 for(int i = 1; i <= n; i++) printf("%d\n", left[i]);//x1[i]这个蚂蚁与x2[left[i]]这个蚂蚁匹配 } return 0; }
相关推荐
ants-go - 开源分、布式、restful golang爬虫引擎
Ansible-ants.zip,ants是一个使用ansible pull管理和应用macos和linux主机配置的框架。,ansible是一个简单而强大的自动化引擎。它用于帮助配置管理、应用程序部署和任务自动化。
線上學習入口網站系統簡介-Ants20050825
singularity exec docker://fnndsc/pl-ants_n4biasfieldcorrection:0.2.7.1 bfc in/ out/ 多线程用于并行化输入。 CPU使用率可以使用等的容器发动机限于docker或podman 。 docker run --rm -u $( id -u ) : $( id ...
运动剂是对我以前的模拟的现代Lua重制。 这不是翻译,而是使用带有友好且流行的Lua语言的开源引擎Löve2D从头开始的翻拍。 最近的截图: (顺便说一句,我正在学习Git / Github,所以在我的第一个开放源代码“?...
ants是一个高性能的协程池,实现了对大规模goroutine的调度管理、goroutine复用,允许使用者在开发并发程序的时候限制协程数量,复用资源,达到更高效执行任务的效果。
ants metaheuristic methods
clojure-ants-simulation:Clojure中Rich Hickey的Ant模拟的重构版本
vue+ant design of vue 商务模板 下载直接使用 可任意修改 -------------------------------------------------------------------------------------
ANTs-2.3.1.zip ANTS2.3.1版本安装包 直接下载解压,亲测可用。
资源分类:Python库 所属语言:Python 使用前提:需要解压 资源全名:ants_client-1.7b1-py2-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
代码蚂蚁Code Ants,MrVal042项目预览
CS-6100-程序-2 蚂蚁寻找食物
ANts-MUTE.ppt 看看
配准ANTs工具的官方介绍文档
为了最大程度地提高其可访问性,ANTS继续专门使用开源和免费提供的软件进行设计,尤其是在现代Linux操作系统上可用的软件。 注意:该项目正在积极开发中,尚未建立稳定的发行分支。 在master分支中可以找到最稳定的...
医学图像处理matlab软件包,在matlab平台下,处理医学图像配准分割的常用软件包指南
ANTS Profiler 5.1.0.15 注册机,可注册ANTS全系列产品。
ants代码性能检查工具