题解
把人走的点当作左部节点，🐕走的当作右部
对于每个人走的节点，如果他与下一个节点的距离的两倍大于某个从当前节点走到右部节点+右部节点走到下一节点的距离，即可连边
输出方案的话，注意到如果右部节点被匹配，match[i]就是匹配它的左部节点，存起来输出即可
代码
|
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 |
#include<bits/stdc++.h> using namespace std; const int MAXN=10003; typedef pair<int,int> P; int Head[MAXN],to[MAXN<<1],Nt[MAXN<<1],tot; int match[MAXN]; bool vis[MAXN]; int rmatch[MAXN]; int n,m; P master[MAXN],dog[MAXN]; double dis(int x_1,int y_1,int x_2,int y_2){ return sqrt((x_1-x_2)*(x_1-x_2)+((y_1-y_2)*(y_1-y_2))); } void add(int x,int y){ Nt[++tot]=Head[x]; to[tot]=y; Head[x]=tot; } int dfs(int x){ for(int i=Head[x],y;i;i=Nt[i]){ if(vis[y=to[i]])continue; vis[y]=1; if(!match[y]||dfs(match[y])){ match[y]=x;return true; } } return false; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ int x,y;cin>>x>>y; master[i]=make_pair(x,y); } for(int i=1;i<=m;i++){ int x,y;cin>>x>>y; dog[i]=make_pair(x,y); } for(int i=1;i<n;i++){ for(int j=1;j<=m;j++){ if(dis(master[i].first,master[i].second,master[i+1].first,master[i+1].second)*2>dis(master[i].first,master[i].second,dog[j].first,dog[j].second)+dis(dog[j].first,dog[j].second,master[i+1].first,master[i+1].second)){ add(i,j+n); } } } int ans=0; for(int i=1;i<n;i++){ memset(vis,0,sizeof(vis)); if(dfs(i))ans++; } printf("%d\n",ans+n); for(int j=1;j<=m;j++){ if(match[j+n]){ rmatch[match[j+n]]=j; } } for(int i=1;i<=n;i++){ printf("%d %d ",master[i].first,master[i].second); if(i!=n&&rmatch[i]){ printf("%d %d ",dog[rmatch[i]].first,dog[rmatch[i]].second); } } return 0; } |