首页 > 代码库 > poj2253

poj2253

2024-07-03 21:18:18   228人阅读

题意：给定n个点，规定两点间的距离为从一个点到另一个点的一系列路径中相邻两点之间欧几里得距离的最大值。现求一号点和二号点之间的最小距离。

思路：prim算法改一下，从一号点开始求最小生成树，直到找到二号点。(ans保存所求路径中的最大值，而不是最后一个)

例：3

999 999

1 1

3 3

output：1408.557

 1 //prim 改
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 const int MAXN = 205;
 6 const int inf = 100000000;
 7 int x[MAXN];
 8 int y[MAXN];
 9 double a[MAXN][MAXN];
10 bool vis[MAXN];
11 double dis[MAXN];
12 int n;
13 double max(double a,double b)
14 {
15     return a>b?a:b;
16 }
17 void pre()
18 {
19     for (int i=0;i<n;i++)
20     {
21         for (int j=0;j<n;j++)
22         {
23            a[i][j]=sqrt((double )(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
24         }
25     }
26 }
27 double prim(int src,int end)
28 {
29     double ans;
30     memset(vis,0,sizeof(vis));
31     for (int i=0;i<n;i++)
32     dis[i]=(double )inf;
33     dis[src]=0;
34     for (int i=0;i<n;i++)
35     {
36         double temp=(double )inf;
37         int k;
38         for (int j=0;j<n;j++)
39         {
40             if (vis[j]) continue;
41             if (temp>dis[j])
42             {
43                 temp=dis[j];
44                 k=j;
45             }
46         }
47         ans=max(ans,temp);
48         if (k==end) return ans;
49         vis[k]=1;
50         for (int j=0;j<n;j++)
51         {
52             if (vis[j]) continue;
53             if (dis[j]>a[k][j])
54             dis[j]=a[k][j];
55         }
56     }
57     return ans;
58 }
59 int main()
60 {
61     int t=0;
62     while (scanf("%d",&n),n)
63     {
64         for (int i=0;i<n;i++)
65         {
66             scanf("%d%d",&x[i],&y[i]);
67         }
68         pre();
69         double ans=prim(0,1);
70 
71         printf("Scenario #%d\n",++t);
72         printf("Frog Distance = %.3f\n\n",ans);
73     }
74     return 0;
75 }
View Code

 


联系
我们