HDOJ---1875スムーズエンジニアリング再接続[prim()アルゴリズム]
13258 ワード
滞りなく工事を再開する
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7210 Accepted Submission(s): 2163
Problem Description
「百島湖」という場所を聞いたことがあると思いますが、百島湖の住民は異なる島に住んでいて、他の島に行きたいときはボートを漕ぐことで実現します.現在、政府は百島湖を大いに発展させることを決定し、発展がまず解決しなければならない問題はもちろん交通問題であり、政府は百島湖の全開通を実現することを決定した.調査チームRPRushが百島湖の状況を十分に理解した後、条件に合った小島の間に橋を建てることにした.条件に合ったのは、2つの小島の間の距離が10メートル以上、1000メートル以上ではないということだ.もちろん、お金を節約するためには、任意の2つの島の間に道があることだけを要求すればいい.このうち橋の価格は100元/メートルです.
Input
入力には複数のデータが含まれます.入力は、まず、Tセットデータを表す整数T(T<=200)を含む.
各グループのデータは、まず整数C(C<=100)であり、小島の個数を表し、次いでCグループの座標であり、各小島の座標を表し、これらの座標は0<=x、y<=1000の整数である.
Output
各入力データのセットは、ブリッジの最小コストを表す行を出力し、結果は小数点以下を保持します.すべてをスムーズにするために工事が実現できない場合は、「oh!」を出力します.
Sample Input
2 2 10 10 20 20 3 1 1 2 2 1000 1000
Sample Output
1414.2 oh!
Author
8600
Source
2008浙大大学院生再試験ウォーミングアップ試合(2)——全真シミュレーション
Recommend
lcy
code:
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 7210 Accepted Submission(s): 2163
Problem Description
「百島湖」という場所を聞いたことがあると思いますが、百島湖の住民は異なる島に住んでいて、他の島に行きたいときはボートを漕ぐことで実現します.現在、政府は百島湖を大いに発展させることを決定し、発展がまず解決しなければならない問題はもちろん交通問題であり、政府は百島湖の全開通を実現することを決定した.調査チームRPRushが百島湖の状況を十分に理解した後、条件に合った小島の間に橋を建てることにした.条件に合ったのは、2つの小島の間の距離が10メートル以上、1000メートル以上ではないということだ.もちろん、お金を節約するためには、任意の2つの島の間に道があることだけを要求すればいい.このうち橋の価格は100元/メートルです.
Input
入力には複数のデータが含まれます.入力は、まず、Tセットデータを表す整数T(T<=200)を含む.
各グループのデータは、まず整数C(C<=100)であり、小島の個数を表し、次いでCグループの座標であり、各小島の座標を表し、これらの座標は0<=x、y<=1000の整数である.
Output
各入力データのセットは、ブリッジの最小コストを表す行を出力し、結果は小数点以下を保持します.すべてをスムーズにするために工事が実現できない場合は、「oh!」を出力します.
Sample Input
2 2 10 10 20 20 3 1 1 2 2 1000 1000
Sample Output
1414.2 oh!
Author
8600
Source
2008浙大大学院生再試験ウォーミングアップ試合(2)——全真シミュレーション
Recommend
lcy
code:
1 #include <iostream>
2 #include <iomanip>
3 #include <fstream>
4 #include <sstream>
5 #include <algorithm>
6 #include <string>
7 #include <set>
8 #include <utility>
9 #include <queue>
10 #include <stack>
11 #include <list>
12 #include <vector>
13 #include <cstdio>
14 #include <cstdlib>
15 #include <cstring>
16 #include <cmath>
17 #include <ctime>
18 #include <ctype.h>
19 using namespace std;
20
21 #define MAXN 1005
22
23 int t,c;
24 double map[MAXN][MAXN];
25 double dis[MAXN];
26 int vst[MAXN];
27
28 typedef struct island
29 {
30 double x,y;
31 }Island;
32 Island island[MAXN];
33
34 double fun_dis(double x1,double y1,double x2,double y2)
35 {
36 return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
37 }
38
39 double prim()
40 {
41 int i,j,k;
42 double mindis,sum=0;
43 for(i=2;i<=c;i++)
44 {
45 vst[i]=0;
46 dis[i]=map[1][i];
47 }
48 vst[1]=1;
49 for(i=2;i<=c;i++)
50 {
51 k=1;
52 mindis=INT_MAX;
53 for(j=2;j<=c;j++)
54 if(!vst[j]&&dis[j]<mindis)
55 {
56 k=j;
57 mindis=dis[j];
58 }
59 if(mindis<INT_MAX)
60 {
61 sum+=mindis;
62 vst[k]=1;
63 }
64 else
65 return INT_MAX;
66 for(j=2;j<=c;j++)
67 if(map[k][j]<dis[j]&&!vst[j])
68 dis[j]=map[k][j];
69 }
70 return sum;
71 }
72
73 int main()
74 {
75 int i,j;
76 double temp;
77 while(~scanf("%d",&t))
78 {
79 while(t--)
80 {
81 scanf("%d",&c);
82 for(i=1;i<=c;i++)
83 scanf("%lf%lf",&island[i].x,&island[i].y);
84 for(i=1;i<=c;i++)
85 for(j=i;j<=c;j++)
86 {
87 temp=fun_dis(island[i].x,island[i].y,island[j].x,island[j].y);
88 if(temp>1000||temp<10)
89 map[i][j]=map[j][i]=INT_MAX;
90 else
91 map[i][j]=map[j][i]=temp;
92 }
93 temp=prim();
94 if(temp<INT_MAX)
95 printf("%.1lf
",temp*100);
96 else
97 printf("oh!
");
98 }
99 }
100 return 0;
101 }