[UVA][匈牙利匹配] 670 - The dog task
The dog task
| The dog task |
Hunter Bob often walks with his dog Ralph. Bob walks with a constant speed and his route is a polygonal line (possibly self- intersecting) whose vertices are specified by N pairs of integers (Xi, Yi) - their Cartesian coordinates.
Ralph walks on his own way but always meets his master at the specified N
points. The dog starts his journey simultaneously with Bob at the point (X1,
Y1) and finishes it also simultaneously with Bob at the point (XN , YN).
Ralph can travel at a speed that is up to two times greater than his master's speed.
While Bob travels in a straight line from one
point to another the cheerful dog seeks trees, bushes, hummocks and all other kinds of
interesting places of the local landscape
which are specified by M pairs of integers (X'j,Y'j). However, after leaving his
master at the point (Xi , Yi) (where
)
the dog visits at most one interesting place before meeting his master again at the point
(
Xi+1 , Yi+1).
Your task is to find the dog's route, which meets the above requirements and allows him to
visit the maximal possible number
of interesting places. The answer should be presented as a polygonal line that represents
Ralph's route. The vertices of this
route should be all points (Xi , Yi) and the maximal number of
interesting places (
X'j, Y'jX). The latter should be visited (i.e.
listed in the route description) at most once.
An example of Bob's route (solid line), a set of interesting places (dots) and one of the
best Ralph's routes (dotted line) are
presented in the following picture:
Input
The first line of the input is an integer L, then a blank line followed by L datasets. There is a blank line between datasets.The first line of each dataset contains two integers N and M, separated
by a space (
). The second
line contains N pairs of integers
,
separated by
spaces, that represent Bob's route. The third line contains M pairs of
integers
,
separated by spaces, that represent interesting places.
All points in the input file are different and their coordinates are integers
not greater than 1000 by the absolute value.
Output
The first line of each dataset should contain the single integer K - the number of vertices of the best dog's route. The second line should contain K pairs of coordinates
,
separated by spaces, that
represent this route. If there are
several such routes, then you may write any of them.
Print a blank line between datasets.
Sample Input
1 4 5 1 4 5 7 5 2 -2 4 -4 -2 3 9 1 2 -1 3 8 -3
Sample Output
6 1 4 3 9 5 7 5 2 1 2 -2 4
Miguel Revilla
2000-05-22
題目描述：
一個狗主人帶著狗去散步，狗主人走的路徑已經固定，然後狗兒可以在主人到達下一個指定
位置前，跑到另一個地方，但要在主人到達下一個指定位置前抵達。
狗的速度是人的兩倍，問狗最多能跑多少地點。
即最大二分匹配。
#include <stdio.h>
#include <string.h>
#include <math.h>
int g[205][205], gt[205];
int mx[205], my[205], used[205];
int dfs(int now) {
int i, x;
for(i = 0; i < gt[now]; i++) {
x = g[now][i];
if(!used[x]) {
used[x] = 1;
if(my[x] == 0 || dfs(my[x])) {
mx[now] = x, my[x] = now;
return 1;
}
}
}
return 0;
}
int main() {
int t, n, m;
int x[105], y[105], X[105], Y[105];
int i, j, k;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++)
scanf("%d %d", &x[i], &y[i]);
for(i = 1; i <= m; i++)
scanf("%d %d", &X[i], &Y[i]);
memset(gt, 0, sizeof(gt));
memset(mx, 0, sizeof(mx));
memset(my, 0, sizeof(my));
for(i = 1; i < n; i++) {
double len = (x[i]-x[i+1])*(x[i]-x[i+1])+
(y[i]-y[i+1])*(y[i]-y[i+1]);
len = 2*sqrt(len);
for(j = 1; j <= m; j++) {
double len1 = (x[i]-X[j])*(x[i]-X[j])+
(y[i]-Y[j])*(y[i]-Y[j]);
double len2 = (x[i+1]-X[j])*(x[i+1]-X[j])+
(y[i+1]-Y[j])*(y[i+1]-Y[j]);
len1 = sqrt(len1), len2 = sqrt(len2);
if(len1+len2 <= len)
g[i][gt[i]++] = j;
}
}
int matched = 0;
for(i = 1; i <= n; i++) {
if(!mx[i]) {
memset(used, 0, sizeof(used));
if(dfs(i))
matched++;
}
}
printf("%d\n", matched+n);
for(i = 1; i <= n; i++) {
if(i != 1) putchar(' ');
printf("%d %d", x[i], y[i]);
if(mx[i])
printf(" %d %d", X[mx[i]], Y[mx[i]]);
}
puts("");
if(t) puts("");
}
}