【题解】Luogu P2526 [SHOI2001] 小狗散步 建图+二分图

将集合点作为左部点，景点作为右部点，跑二分图最大匹配

主要是建图不太好想

考虑什么时候小狗能和主人汇合，因为小狗的速度可以是主人的两倍

枚举每个集合点和景点，如果主人从集合点$A$到集合点$B$的距离大于小狗从集合点$A$到景点再到集合点B的距离$÷2$就可以连边

code

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 namespace gengyf{
 4 #define ll long long
 5 const int maxn=110;
 6 const int inf=1e9+7;
 7 inline int read(){
 8     int f=1,x=0;char s=getchar();
 9     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
10     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
11     return f*x;
12 }
13 int n,m,ans,a[maxn][maxn];
14 struct node{
15     int xx,yy;
16 }x[maxn],y[maxn];
17 int vis[maxn],match[maxn];
18 bool dfs(int x){
19     for(int y=1;y<n;y++){
20         if(!vis[y]&&a[x][y]){
21             vis[y]=1;
22             if(!match[y]||dfs(match[y])){
23                 match[y]=x;return true;
24             }
25         }
26     }
27     return false;
28 }
29 int abs(int x){
30     return x<0?-x:x;
31 }
32 double dist(node a,node b){
33     double x=abs(a.xx-b.xx),y=abs(a.yy-b.yy);
34     return sqrt(x*x+y*y);
35 }
36 int main(){
37     n=read();m=read();
38     for(int i=1;i<=n;i++){
39         x[i].xx=read();x[i].yy=read();
40     }
41     for(int i=1;i<=m;i++){
42         y[i].xx=read();y[i].yy=read();
43     }
44     for(int i=1;i<n;i++)
45         for(int j=1;j<=m;j++){
46             if(dist(x[i],x[i+1])>(dist(x[i],y[j])+dist(y[j],x[i+1]))/2.0){
47                 a[j][i]=1;
48             }
49         }
50     for(int i=1;i<=m;i++){
51         memset(vis,0,sizeof(vis));
52         if(dfs(i))ans++;
53     }
54     printf("%d\n",ans+n);
55     for(int i=1;i<=n;i++){
56         printf("%d %d",x[i].xx,x[i].yy);
57         if(i==n){
58             printf("\n");
59         }
60         else {
61             printf(" ");
62             if(match[i]){
63                 printf("%d %d ",y[match[i]].xx,y[match[i]].yy);
64             }
65         }
66     }
67     return 0;
68 }
69 }
70 signed main(){
71   gengyf::main();
72   return 0;
73 }

View Code

哦对了，这题是Special Judge，样例不一样是因为二分图匹配本来就不唯一