poj 1034 The dog task

本文从WordPress迁移而来, 查看全部WordPress迁移文章

二分图

题意:给出n个点的坐标,表示人走的路线,人会按着这n个点的顺序来走,速度是1。狗一开始也在点1,狗的速度是2。

另外给出m个幸运点,狗希望去到这些幸运点,但是人从i点走到i+1点的时候,狗可以从i点走到一个幸运点,然后必须马上返回到i+1点(赶在人到达前到达或同时到达),并且每次只能去一个幸运点。求狗最多能去多少个幸运点。最后输出狗一共走过的路径长度和每个点的坐标

把路径中的(i,i+1)打包看做一个X点,把每个幸运点看做一个Y点。对于幸运点j,如果狗可以在i点去到j点再回到i+1点,那么就在X和Y间连接一条线,就形成了二分图模型,求一下最大匹配即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
using namespace std;
#define N 110
#define M 10010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

int n,m,tot,head[N];
struct edge{
int v,next;
}e[M];
struct point{
int x,y;
}a[N],b[N];
int match[N];
bool vis[N];

inline double dis(point p ,point q){
return sqrt(1. * (p.x-q.x)*(p.x-q.x) + 1. * (p.y-q.y)*(p.y-q.y));
}

inline void add(int u,int v){
e[tot].v = v; e[tot].next = head[u]; head[u] = tot++;
}

int dfs(int u){
for(int k = head[u]; k != -1; k = e[k].next){
int v = e[k].v;
if(!vis[v]){
vis[v] = true;
if(match[v] == -1 || dfs(match[v])){
match[v] = u; return 1;
}
}
}
return 0;
}

void MaxMatch(){
int ans = 0;
cl(match,-1);
for(int i = 1; i <= m; i++){
cl(vis,false);
ans += dfs(i);
}
printf("%d\n",n+ans);
for(int i = 1; i < n; i++){
printf("%d %d ",a[i].x,a[i].y);
if(match[i] != -1){
int id = match[i];
printf("%d %d ",b[id].x , b[id].y);
}
}
printf("%d %d\n",a[n].x,a[n].y);
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
for(int i = 1; i <= n; i++){
scanf("%d%d",&a[i].x , &a[i].y);
}
for(int i = 1; i <= m; i++){
scanf("%d%d",&b[i].x , &b[i].y);
}
tot = 0; cl(head,-1);
for(int i = 1; i < n; i++)
for(int j = 1; j <= m; j++){
double d1 = dis(a[i],a[i+1]);
double d2 = dis(a[i],b[j]) + dis(b[j],a[i+1]);
if(d2/2 <= d1) add(j,i);
}
MaxMatch();
}
return 0;
}