将集合点作为左部点，景点作为右部点，跑二分图最大匹配
主要是建图不太好想
考虑什么时候小狗能和主人汇合，因为小狗的速度可以是主人的两倍
枚举每个集合点和景点，如果主人从集合点$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 ",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(" "); 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 }
哦对了，这题是Special Judge，样例不一样是因为二分图匹配本来就不唯一