poj2253 Frogger（最短路变型或者最小生成树）
生活随笔
收集整理的這篇文章主要介紹了
poj2253 Frogger（最短路变型或者最小生成树）
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
1 /*
2 題意：就是源點(diǎn)到終點(diǎn)有多條的路徑，每一條路徑中都有一段最大的距離！
3 求這些路徑中最大距離的最小值！
4
5 Dijkstra, Floyd, spfa都是可以的！只不過是將松弛的條件變一下就行了！
6
7 想了一下，這道題用最小生成樹做也可以啊，圖總是連通的嘛!所以建一棵最小
8 生成樹，然后dfs一下，從源點(diǎn)1，到終點(diǎn)2的路徑上，查找邊長最大的路徑！
9 附上代碼.....
10 */
11 #include<iostream>
12 #include<cstdio>
13 #include<algorithm>
14 #include<cstring>
15 #include<cmath>
16 #include<iomanip>
17 #define INF 0x3f3f3f3f*1.0
18 using namespace std;
19 struct node{
20 double x, y;
21 };
22 node nd[205];
23 double g[205][205];
24 double d[205];
25 int vis[205];
26 int n;
27
28 void Dijkstra(){
29 memset(vis, 0, sizeof(vis));
30 d[1]=0.0;
31 int root=1;
32 vis[1]=1;
33 for(int i=2; i<=n; ++i)
34 d[i]=INF;
35 for(int j=1; j<n; ++j){
36 int p;
37 double minL=INF;
38 for(int i=1; i<=n; ++i){
39 double dist;
40 if(!vis[i] && d[i]> (dist=max(d[root], g[root][i])))
41 d[i]=dist;
42 if(!vis[i] && minL>d[i]){
43 minL=d[i];
44 p=i;
45 }
46 }
47 if(minL==INF) return;
48 root=p;
49 vis[root]=1;
50 }
51 }
52
53 int main(){
54 int cnt=0;
55 while(cin>>n && n){
56 for(int i=1; i<=n; ++i)
57 for(int j=1; j<=n; ++j)
58 g[i][j]=INF;
59 for(int i=1; i<=n; ++i){
60 double u, v;
61 cin>>nd[i].x>>nd[i].y;
62 for(int j=1; j<i; ++j){
63 u=nd[i].x-nd[j].x;
64 v=nd[i].y-nd[j].y;
65 g[i][j]=g[j][i]=sqrt(u*u + v*v);
66 }
67 }
68 Dijkstra();
69 cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
70 cout<<fixed<<setprecision(3)<<d[2]<<endl;
71 cout<<endl;
72 }
73 return 0;
74 }
75
76 //最小生成樹思想
77 #include<iostream>
78 #include<cstdio>
79 #include<algorithm>
80 #include<cstring>
81 #include<cmath>
82 #include<iomanip>
83 #define INF 0x3f3f3f3f*1.0
84 using namespace std;
85 struct node{
86 double x, y;
87 };
88 node nd[205];
89
90 struct EDGE{
91 int u, v;
92 double dist;
93 };
94 EDGE edge[21000];
95
96 bool cmp(EDGE a, EDGE b){
97 return a.dist < b.dist;
98 }
99
100 double g[205][205];
101
102 int vis[205], f[205];
103 int n;
104
105 int getFather(int x){
106 return x==f[x] ? x : f[x]=getFather(f[x]);
107 }
108
109 bool Union(int a, int b){
110 int fa=getFather(a), fb=getFather(b);
111 if(fa!=fb){
112 f[fa]=fb;
113 return true;
114 }
115 return false;
116 }
117 double dd;
118 bool dfs(int cur, double ddd){
119 vis[cur]=1;
120 if(cur==2){
121 dd=ddd;
122 return true;
123 }
124 for(int i=1; i<=n; ++i)
125 if(g[cur][i]!=INF && !vis[i]){
126 if(ddd<g[cur][i]){
127 if(dfs(i, g[cur][i])) return true;
128 }
129 else if(dfs(i, ddd)) return true;
130 }
131 return false;
132 }
133
134 int main(){
135 int cnt=0;
136 while(cin>>n && n){
137 for(int i=1; i<=n; ++i)
138 for(int j=1; j<=n; ++j)
139 g[i][j]=INF;
140 int count=0;
141 for(int i=1; i<=n; ++i){
142 double u, v;
143 cin>>nd[i].x>>nd[i].y;
144 for(int j=1; j<i; ++j){
145 u=nd[i].x-nd[j].x;
146 v=nd[i].y-nd[j].y;
147 edge[count].u=i;
148 edge[count].v=j;
149 edge[count++].dist=sqrt(u*u + v*v);
150 }
151 }
152 sort(edge, edge+count, cmp);
153 for(int i=1; i<=n; ++i)
154 f[i]=i;
155 for(int i=0; i<count; ++i){
156 int u, v;
157 if(Union(u=edge[i].u, v=edge[i].v))
158 g[u][v]=g[v][u]=edge[i].dist;
159 }
160 memset(vis, 0, sizeof(vis));
161 dfs(1, 0.0);
162 cout<<"Scenario #"<<++cnt<<endl<<"Frog Distance = ";
163 cout<<fixed<<setprecision(3)<<dd<<endl;
164 cout<<endl;
165 }
166 return 0;
167 }
?
轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/3915234.html
總結(jié)
以上是生活随笔為你收集整理的poj2253 Frogger（最短路变型或者最小生成树）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 甲骨文酒的品质真的让人惊艳吗？
- 下一篇： 雅迪奥抗皱紧致霜有用过的吗？效果怎么样？