題目背景

Grant喜歡帶著他的小狗Pandog散步。Grant以一定的速度沿著固定路線走，該路線可能自交。Pandog喜歡游覽沿途的景點，不過會在給定的N個點和主人相遇。小狗和主人同時從(X1，Y1)點出發，并同時在(Xn，Yn)點匯合。小狗的速度最快是Grant的兩倍。當主人從一個點以直線走向另一個點時，Pandog跑向一個它感興趣的景點。Pandog每次與主人相遇之前最多只去一個景點。

題目描述

你現在的任務是：為Pandog尋找一條路線(有可能與主人的路線部分相同)，使它能夠游覽最多的景點，并能夠準時與主人在給定地點相遇或者匯合。

輸入輸出格式

輸入格式：

?

輸入文件第一行是兩個整數N和M( 1≤N，M≤100 )；

輸入文件第二行的N個坐標給出了Grant的散步路線，即Pandog和主人相遇地點；

輸入文件第三行的M個坐標給出了所有Pandog感興趣的景點。

所有輸入的坐標均不相同，且絕對值不超過1000。

?

輸出格式：

?

輸出小狗的移動路線。

第一行是經過的點數，第二行依次為經過的點的坐標(直角坐標系)

?

輸入輸出樣例

輸入樣例#1：
4 5 1 4 5 7 5 2 -2 4 -4 -2 3 9 1 2 -1 3 8 -3 輸出樣例#1：
6 1 4 3 9 5 7 5 2 1 2 -2 4

?

題解

• 可以發現，主人的路線是一定的，我們可以預處理出當前主人在x，小狗可以瀏覽的景點個數，存在一個數組里
• 因為我們要求的是小狗最多瀏覽的景點數，那么顯然可以最大匹配
• 然后就沒了

代碼

1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <cmath> 5 #define N 110 6 #define sqr(x) (x)*(x) 7 using namespace std; 8 struct edge {int x,y;}a[N],b[N]; 9 int n,m,map[N][N],vis[N],p[N],ans=0; 10 double calc(edge x,edge y) { return sqrt(sqr(x.x-y.x)+sqr(x.y-y.y)); } 11 int xyl(int x) 12 { 13 for (int i=1;i<n;i++) 14 if (map[x][i]&&!vis[i]) 15 { 16 vis[i]=1; 17 if (!p[i]||xyl(p[i])) { p[i]=x; return 1; } 18 } 19 return 0; 20 } 21 int main() 22 { 23 scanf("%d%d",&n,&m); 24 for (int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); 25 for (int i=1;i<=m;i++) scanf("%d%d",&b[i].x,&b[i].y); 26 for (int i=1;i<=n;i++) 27 for (int j=1;j<=m;j++) 28 if (calc(a[i],a[i+1])*2>calc(a[i],b[j])+calc(b[j],a[i+1])) 29 map[j][i]=1; 30 for (int i=1;i<=m;i++) memset(vis,0,sizeof(vis)),ans+=xyl(i); 31 printf("%d\n",ans+n); 32 for (int i=1;i<=n;i++) 33 { 34 printf("%d %d ",a[i].x,a[i].y); 35 if (i<n&&p[i]) printf("%d %d ",b[p[i]].x,b[p[i]].y); 36 } 37 }

?

轉載于:https://www.cnblogs.com/Comfortable/p/10296289.html

總結

以上是生活随笔為你收集整理的[匈牙利] 洛谷 P2526 小狗散步的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。