KM Composition for minimum weight matching

Ensure the minimum weight , The connected edges must be disjoint .

Time Limit: 3000MS |
Memory Limit: Unknown |
64bit IO Format: %lld & %llu |

Description

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* ant colonies and *n* 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* 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*(1*n*100) --

the number of ant colonies and apple trees. It is followed by *n* lines describing *n* ant colonies, followed by *n* lines describing *n* apple

trees. Each ant colony and apple tree is described by a pair of integer coordinates *x* and *y*(- 10000*x*, *y*10000) 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* lines with one integer number on each line. The number written on *i* -th line denotes the number

(from 1 to *n* ) of the apple tree that is connected to the *i* i -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

Source

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath> using namespace std; const int maxn=220;

const double INF=999999999999999.;

const double eps=1e-5; struct Dian

{

double x,y;

}white[maxn*maxn],black[maxn*maxn]; int n;

double g[maxn][maxn];

int linker[maxn*maxn];

double lx[maxn*maxn],ly[maxn*maxn];

double slack[maxn*maxn];

bool visx[maxn*maxn],visy[maxn*maxn]; bool dfs(int x)

{

visx[x]=true;

for(int y=0;y<n;y++)

{

if(visy[y]) continue;

double tmp=lx[x]+ly[y]-g[x][y];

if(fabs(tmp)<eps)

{

visy[y]=true;

if(linker[y]==-1||dfs(linker[y]))

{

linker[y]=x;

return true;

}

}

else if(slack[y]>tmp)

slack[y]=tmp;

}

return false;

} int KM()

{

memset(linker,-1,sizeof(linker));

memset(ly,0,sizeof(ly));

for(int i=0;i<n;i++)

{

lx[i]=-INF;

for(int j=0;j<n;j++)

if(g[i][j]>lx[i])

lx[i]=g[i][j];

}

for(int x=0;x<n;x++)

{

for(int i=0;i<n;i++)

slack[i]=INF;

while(true)

{

memset(visx,false,sizeof(visx));

memset(visy,false,sizeof(visy));

if(dfs(x)) break;

double d=INF;

for(int i=0;i<n;i++)

if(!visy[i]&&d>slack[i])

d=slack[i];

for(int i=0;i<n;i++)

if(visx[i])

lx[i]-=d;

for(int i=0;i<n;i++)

if(visy[i])

ly[i]+=d;

else

slack[i]-=d;

}

}

} double Dist(Dian a,Dian b)

{

return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

} int main()

{

bool first=false;

while(scanf("%d",&n)!=EOF)

{

if(first) putchar(10);

else first=true;

for(int i=0;i<n;i++)

{

double a,b;

scanf("%lf%lf",&a,&b);

white[i]=(Dian){a,b};

}

for(int i=0;i<n;i++)

{

double a,b;

scanf("%lf%lf",&a,&b);

black[i]=(Dian){a,b};

}

for(int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

double t=Dist(black[i],white[j]);

g[i][j]=-t;

}

}

KM();

for(int i=0;i<n;i++)

{

printf("%d\n",linker[i]+1);

}

}

return 0;

}

## UVALive 4043 Ants More articles about

- UVALive 4043 Ants Ant （ The best perfect match of bipartite graph ,KM Algorithm ）
The question : Yes n An ant n tree , Ants and trees need to pair up , Connect a line segment between the successful pair , All line segments must not intersect . Output the matching tree in order . Ideas : This topic is really a skill , You can't use greed to choose the nearest tree for each ant , It's very likely that ...

- UVALive 4043 Ants( Bipartite graphs match perfectly )
The question : Each colony has its own food source ( apple ), Ants are known to know their way by smell , So the trajectory of the ant colony can't overlap . Now, in the coordinate system n An ant colony and n The coordinates of a fruit tree , Pairing , Achieve the above requirements . The output of the i Line representation i An ant colony ...

- UVaLive 4043 Ants ( The perfect match )
The question : Given n An ant and n The coordinates of a tree , Ask how to match so that each ant's line to the tree doesn't intersect . Analysis : You can think of ants and trees as two categories , Then it's a perfect match , But their connections don't intersect , Then you have to think about , The best match is ...

- Uvalive 4043 Ants —— Maximum weight matching of bipartite graphs KM Algorithm
Topic link :https://vjudge.net/problem/UVALive-4043 The question : give n A white dot and n The coordinates of a black spot , Asked to use n Two disjoint lines connect them , Each line segment connects a white dot and a black dot ...

- Training guide UVALive - 4043（ Bipartite map matching + KM Algorithm ）
layout: post title: Training guide UVALive - 4043( Bipartite map matching + KM Algorithm ) author: "luowentaoaa" catalog: true ...

- LA - 4043 - Ants
The question :n Only ants ,n tree , Each ant connects to a tree , attachment ( A straight line ) Can't intersect , give n Only ants and n The coordinates of a tree , Output n The number of the tree that the ant is paired with (1 <= n <= 100, -10000 <= coordinate x, ...

- UVALive 4043 Transform the best perfect match
First of all, the black and white dots make up a bipartite graph. There's no doubt about that The key is that all the black and white lines required in the title should not be crossed ... At first, I didn't know how to translate this into an algorithm in bipartite graph . Later I found out from reading , If you cross two by two , Then you can use the two lines as diagonals of a quadrilateral , ...

- UVALive 7505 Hungry Game of Ants (2015Ecfinal)
The question : The length is n The number of the point on the line segment of is from 1~n, Each point has an ant whose weight is equal to the number of the point , At first, each ant can choose to walk to the right or to the left. When two ants meet, the heavier one will eat the smaller one, and the weight will be the sum of the two , Turn around when you get to the border , ask ...

- UVa 12709 && UVaLive 6650 Falling Ants ( Water problem )
The question : Given n The length of a cuboid , wide , high , What is the maximum volume when you seek the maximum height . Analysis : Sort , Just sort by height and volume . The code is as follows : #pragma comment(linker, "/STACK:1024 ...

## Random recommendation

- Chapter two JavaScript grammar ·
javascript Code placement : 1. Put the code in the document <head> In the tag <script> Between the labels : 2. Save the code with an extension of .js A separate file of . The typical approach is in the documentation of <h ...

- from setTimeout To talk about JavaScript Operating mechanism
from setTimeout Speaking of as everyone knows ,JavaScript It's single threaded programming , What is single thread , That is to say, at the same time JavaScript Only one piece of code can be executed , If this code takes a long time to execute , Then the following code can only wait for it to execute ...

- JAVASE02-Unit02： Regular expressions 、 Object 、 Packaging
Regular expressions . Object . Packaging String support regular expression method 1 : package day02; /** * String support regular expression method 1 : * boolean matches(String r ...

- NSUrl Printing of
1 from http://my.oschina.net/wangdk/blog/165554: NSURL *url = [NSURL URLWithString:@"http://www.ba ...

- stay jsp Page parsing json Of 2 Methods
Method 1: $(function() { $("#btn").click(function() { $.ajax({ url : "fastjson.do", s ...

- sqlserver About affairs
Four characteristics of transactions : Atomicity , Uniformity , persistence , Isolation, Atomicity : Atomicity : Indicates that a transaction is executed as an atom , An integral , The whole statement either executes , Or not sqlserver Each individual statement in the transaction can be regarded as contained in the transaction, and each sentence has its own ...

- IOS Apple buys PHP Server side validation ( Subscription purchase and one-time purchase are common )
// Formal environmental verification address $ios_verify_url = 'https://buy.itunes.apple.com/verifyReceipt'; // Test environment verification address $ios_sandbox ...

- Markdown Write interface documentation , Automatic addition TOC
Last time when it comes to , use Impress.js Instead of PPT To do a project presentation . This time Markdown Let's do the interface documentation .( I can't say it's a substitute for Word, I can only say that I feel more convenient ) Of course , It should be supplemented by Git, To facilitate version management . Markdown ...

- How novices learn python(python Learning Roadmap )
Now Internet giants , They've all switched to artificial intelligence , And the best programming language for AI is python, The future is clear . This is a small make-up for you to sort out python Learning Roadmap , Follow this tutorial step by step , It must be right python There's something more profound ...

- turn : JQuery this and $(this) The difference and acquisition of $(this) Methods of child element objects
1.JQuery this and $(this) The difference between Believe a lot of new contacts JQuery People who , A lot of them will be right $(this) and this The difference between them is vague , So what's the difference between the two ? So let's see first JQuery Medium $() this ...