题目描述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​)走向(Xi1,Yi1)(X_{i1}, Y_{i1})(Xi1​,Yi1​)的每一段路程中狗可以在离开Bob\texttt{Bob}Bob后访问至多一个兴趣点然后再与Bob\texttt{Bob}Bob在该段的终点会合。给定MMM个兴趣点的坐标要求规划狗的路线使其访问尽可能多的兴趣点并输出路线包括所有Bob\texttt{Bob}Bob的路径点和被访问的兴趣点。输入格式第一行为整数LLL表示数据集个数。每组数据第一行为两个整数NNN和MMM2≤N≤1002 \le N \le 1002≤N≤1000≤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到点i1i1i1每个线段是一个“位置”狗最多可以在该线段上访问一个兴趣点。若狗在Bob\texttt{Bob}Bob走完第iii段时从iii点出发访问兴趣点jjj再到达i1i1i1点且所用时间不超过Bob\texttt{Bob}Bob走完该段所需时间的两倍则称兴趣点jjj对线段iii是可达的。目标是给每个线段匹配一个兴趣点线段不能重复匹配使得匹配数最大即狗访问的兴趣点最多。判断可达性设Bob\texttt{Bob}Bob从AAA到BBB的距离为dABd_{AB}dAB​狗从AAA到兴趣点PPP到BBB的距离为dAPdPBd_{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倍即dAPdPBvdog≤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}vdog​dAP​dPB​​≤vbob​dAB​​且vdog​≤2vbob​最宽松情况下vdog2vbobv_{dog} 2 v_{bob}vdog​2vbob​所以条件为dAPdPB≤2⋅dAB d_{AP} d_{PB} \le 2 \cdot d_{AB}dAP​dPB​≤2⋅dAB​即狗绕行总长度不超过Bob\texttt{Bob}Bob直线距离的两倍。解题思路对于Bob\texttt{Bob}Bob的每一段(i,i1)(i, i1)(i,i1)和每个兴趣点jjj计算三个距离dABd_{AB}dAB​Bob\texttt{Bob}Bob段长、dAPd_{AP}dAP​AAA到兴趣点、dPBd_{PB}dPB​兴趣点到BBB。若dAPdPB2⋅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点若该线段匹配了某个兴趣点则在该点后输出该兴趣点坐标。最后输出终点。注意输出路线顶点数为Nmatch_countN \textit{match\_count}Nmatch_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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXV110;constdoubleEPSILON1e-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){doubledistABsqrt(pow(a.x-b.x,2)pow(a.y-b.y,2));doubledistACsqrt(pow(a.x-c.x,2)pow(a.y-c.y,2));doubledistBCsqrt(pow(b.x-c.x,2)pow(b.y-c.y,2));returndistACdistBC2.0*distAB-EPSILON;}intdfs(intu){for(intv0;vM;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(){intmatches0;memset(cx,-1,sizeof(cx));memset(cy,-1,sizeof(cy));for(inti0;iN;i)if(cx[i]-1){memset(visited,0,sizeof(visited));matchesdfs(i);}returnmatches;}intmain(){cinL;for(intcases1;casesL;cases){if(cases1)cout\n;cinNM;for(inti0;iN;i)cinbob[i].xbob[i].y;for(inti0;iM;i)cindog[i].xdog[i].y;memset(g,0,sizeof(g));for(inti0;iN-1;i)for(intj0;jM;j)if(accessible(bob[i],bob[i1],dog[j]))g[i][j]1;cout(Nhungarian())\n;for(inti0;iN-1;i){coutbob[i].x bob[i].y ;if(cx[i]0)coutdog[cx[i]].x dog[cx[i]].y ;}coutbob[N-1].x bob[N-1].y\n;}return0;}总结本题通过将每段Bob\texttt{Bob}Bob路径视为一个“容器”将兴趣点视为可分配的资源利用二分图匹配求最大访问数。关键点包括正确判断狗在给定速度限制下是否能绕行访问兴趣点。使用匈牙利算法求最大匹配。输出路线时按顺序插入匹配的兴趣点。该解法是二分图匹配在路径规划中的典型应用适用于小规模数据。