题目描述
Bob\texttt{Bob}Bob沿一条由NNN个点组成的折线匀速行走，Ralph\texttt{Ralph}Ralph是Bob\texttt{Bob}Bob的狗，它也在同一时间从起点出发，在终点与Bob\texttt{Bob}Bob同时到达。狗的速度最多是Bob\texttt{Bob}Bob的222倍。在Bob\texttt{Bob}Bob从点(Xi,Yi)(X_i, Y_i)(Xi,Yi)走向(Xi+1,Yi+1)(X_{i+1}, Y_{i+1})(Xi+1,Yi+1)的每一段路程中，狗可以在离开Bob\texttt{Bob}Bob后访问至多一个兴趣点，然后再与Bob\texttt{Bob}Bob在该段的终点会合。给定MMM个兴趣点的坐标，要求规划狗的路线，使其访问尽可能多的兴趣点，并输出路线（包括所有Bob\texttt{Bob}Bob的路径点和被访问的兴趣点）。
输入格式
第一行为整数LLL，表示数据集个数。每组数据第一行为两个整数NNN和MMM（2≤N≤1002 \le N \le 1002≤N≤100，0≤M≤1000 \le M \le 1000≤M≤100）。第二行包含2N2N2N个整数，表示Bob\texttt{Bob}Bob路径的NNN个点坐标。第三行包含2M2M2M个整数，表示MMM个兴趣点坐标。各组之间用空行分隔。
输出格式
对于每组数据，第一行输出狗路线中的顶点数KKK。第二行输出KKK对坐标（按顺序），表示狗的路线。每组输出之间用空行分隔。
样例
输入
1 4 5 1 4 5 7 5 2 -2 4 -4 -2 3 9 1 2 -1 3 8 -3输出
6 1 4 3 9 5 7 5 2 1 2 -2 4题目分析
本题可建模为二分图匹配问题。Bob\texttt{Bob}Bob的路径有N−1N-1N−1个线段（从点iii到点i+1i+1i+1），每个线段是一个“位置”，狗最多可以在该线段上访问一个兴趣点。若狗在Bob\texttt{Bob}Bob走完第iii段时，从iii点出发，访问兴趣点jjj，再到达i+1i+1i+1点，且所用时间不超过Bob\texttt{Bob}Bob走完该段所需时间的两倍，则称兴趣点jjj对线段iii是可达的。目标是给每个线段匹配一个兴趣点（线段不能重复匹配），使得匹配数最大，即狗访问的兴趣点最多。
判断可达性：设Bob\texttt{Bob}Bob从AAA到BBB的距离为dABd_{AB}dAB，狗从AAA到兴趣点PPP到BBB的距离为dAP+dPBd_{AP} + d_{PB}dAP+dPB。狗的速度最多为Bob\texttt{Bob}Bob的222倍，因此狗走完A→P→BA \to P \to BA→P→B所需时间不超过Bob\texttt{Bob}Bob走完A→BA \to BA→B时间的222倍，即：
dAP+dPBvdog≤dABvbob且vdog≤2vbob \frac{d_{AP} + d_{PB}}{v_{dog}} \le \frac{d_{AB}}{v_{bob}} \quad \text{且} \quad v_{dog} \le 2 v_{bob}vdogdAP+dPB≤vbobdAB且vdog≤2vbob
最宽松情况下，vdog=2vbobv_{dog} = 2 v_{bob}vdog=2vbob，所以条件为：
dAP+dPB≤2⋅dAB d_{AP} + d_{PB} \le 2 \cdot d_{AB}dAP+dPB≤2⋅dAB
即狗绕行总长度不超过Bob\texttt{Bob}Bob直线距离的两倍。
解题思路
- 对于Bob\texttt{Bob}Bob的每一段(i,i+1)(i, i+1)(i,i+1)和每个兴趣点jjj，计算三个距离：dABd_{AB}dAB（Bob\texttt{Bob}Bob段长）、dAPd_{AP}dAP（AAA到兴趣点）、dPBd_{PB}dPB（兴趣点到BBB）。若dAP+dPB<2⋅dAB−ϵd_{AP} + d_{PB} < 2 \cdot d_{AB} - \epsilondAP+dPB<2⋅dAB−ϵ（使用浮点数比较），则建立边g[i][j]=1g[i][j] = 1g[i][j]=1。
- 使用匈牙利算法求二分图最大匹配，左侧为N−1N-1N−1个线段，右侧为MMM个兴趣点。最大匹配数即为狗最多能访问的兴趣点数。
- 输出狗的路线：从起点开始，依次输出每个Bob\texttt{Bob}Bob点，若该线段匹配了某个兴趣点，则在该点后输出该兴趣点坐标。最后输出终点。
注意：输出路线顶点数为N+match_countN + \textit{match\_count}N+match_count。
复杂度分析
- 建图：O((N−1)⋅M)O((N-1) \cdot M)O((N−1)⋅M)，N,M≤100N, M \le 100N,M≤100。
- 匈牙利算法：O((N−1)2⋅M)O((N-1)^2 \cdot M)O((N−1)2⋅M)，实际很小。
- 总时间可忽略。
代码实现
// The Dog Task// UVa ID: 670// Verdict: Accepted// Submission Date: 2016-11-09// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXV=110;constdoubleEPSILON=1e-20;structpoint{intx,y;};point bob[MAXV],dog[MAXV];intg[MAXV][MAXV],visited[MAXV],cx[MAXV],cy[MAXV],L,N,M;boolaccessible(point a,point b,point c){doubledistAB=sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));doubledistAC=sqrt(pow(a.x-c.x,2)+pow(a.y-c.y,2));doubledistBC=sqrt(pow(b.x-c.x,2)+pow(b.y-c.y,2));returndistAC+distBC<2.0*distAB-EPSILON;}intdfs(intu){for(intv=0;v<M;v++)if(g[u][v]&&!visited[v]){visited[v]=1;if(cy[v]==-1||dfs(cy[v])){cx[u]=v;cy[v]=u;return1;}}return0;}inthungarian(){intmatches=0;memset(cx,-1,sizeof(cx));memset(cy,-1,sizeof(cy));for(inti=0;i<N;i++)if(cx[i]==-1){memset(visited,0,sizeof(visited));matches+=dfs(i);}returnmatches;}intmain(){cin>>L;for(intcases=1;cases<=L;cases++){if(cases>1)cout<<'\n';cin>>N>>M;for(inti=0;i<N;i++)cin>>bob[i].x>>bob[i].y;for(inti=0;i<M;i++)cin>>dog[i].x>>dog[i].y;memset(g,0,sizeof(g));for(inti=0;i<N-1;i++)for(intj=0;j<M;j++)if(accessible(bob[i],bob[i+1],dog[j]))g[i][j]=1;cout<<(N+hungarian())<<'\n';for(inti=0;i<N-1;i++){cout<<bob[i].x<<' '<<bob[i].y<<' ';if(cx[i]>=0)cout<<dog[cx[i]].x<<' '<<dog[cx[i]].y<<' ';}cout<<bob[N-1].x<<' '<<bob[N-1].y<<'\n';}return0;}总结
本题通过将每段Bob\texttt{Bob}Bob路径视为一个“容器”，将兴趣点视为可分配的资源，利用二分图匹配求最大访问数。关键点包括：
- 正确判断狗在给定速度限制下是否能绕行访问兴趣点。
- 使用匈牙利算法求最大匹配。
- 输出路线时按顺序插入匹配的兴趣点。
该解法是二分图匹配在路径规划中的典型应用，适用于小规模数据。
