404 / 360 / 36
Регистрация: 11.10.2010
Сообщений: 1,907
|
|
|
1
|
Алгоритм Крускала
13.04.2012, 21:56. Показов 6953. Ответов 2
Задача:
Тимур и его друзья, приехав летом на свои старые дачи, решили устроить на время своего отдыха игру. Они организовали команду, чтобы тайно помогать жителям дачного городка в их повседневных делах.
Дачный городок довольно большой, и дома, в которых живут друзья Тимура, расположены далеко друг от друга. Как быстро передавать друг другу сообщения? Как собирать ребят на совет?
Тимур решил проложить веревочный телеграф, который связал бы все домики, в которых живут ребята из его команды.
Всего домиков N. По карте ребята вычислили координаты каждого домика (Xi, Yi) в целых числах и выписали их на бумаге. За единицу измерения координат они взяли один метр. Однако возник вопрос: Какие домики нужно соединять веревочным телеграфом, чтобы связь была между всеми домиками (возможно, через другие домики), а общая длина всех веревок была как можно меньше?
Требуется написать программу, которая по координатам домиков определяла бы, какова минимальная общая длина всех веревок, соединяющих все домики между собой (возможно, через другие домики).
Порядок ввода:
Порядок вывода:
X.xx
где X.xx - минимальная общая длина веревки с точностью до двух знаков в дробной части.
Пример ввода:
5
100 200
200 200
300 400
400 200
400 100
Пример вывода:
Органичения:
0 < N <= 100
-32000 <= Xi, Yi <= 32000
я решил ее с помощью алгоритма Прима
вот мое решение | C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#define INF 1000000000
using namespace std;
int main()
{
ifstream cin("input.txt");
ofstream cout("output.txt");
int n;
cin >> n;
vector< vector<float> > g(n,vector<float>(n,0));
vector<int> x(n),y(n);
for (int i=0;i<n;i++)
cin >> x[i] >> y[i];
for (int i=0;i<n;i++)
for (int j=0;j<n;j++)
g[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
vector<bool> used(n);
vector<float> min_e(n,INF);
vector<int> sel_e(n,-1);
min_e[0]=0;
for (int i=0;i<n;i++)
{
int v=-1;
for (int j=0;j<n;j++)
if (!used[j] && (v==-1 || min_e[j]<min_e[v]))
v=j;
used[v]=1;
for (int j=0;j<n;j++)
if (!used[j] && g[v][j]<min_e[j])
{
min_e[j]=g[v][j];
sel_e[j]=v;
}
}
float dist=0;
for (int i=1;i<n;i++)
dist+=g[i][sel_e[i]];
cout << std::fixed << setprecision(2) << dist;
return 0;
} |
|
но некак немогу решить ее с помощью алгоритма Крускала
вот мой код | C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <fstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> p;
vector<int> r;
void make_set(int v)
{
p[v]=v;
r[v]=0;
}
int find_set(int v)
{
return (v==p[v] ? v : p[v]=find_set(p[v]));
}
void union_sets(int a,int b)
{
a=find_set(a);
b=find_set(b);
if (a!=b)
{
if (r[a]<r[b])
swap(a,b);
p[b]=a;
if (r[a]==r[b])
++r[a];
}
}
int main()
{
ifstream cin("input.txt");
ofstream cout("output.txt");
int n,m=0;
vector< pair< float,pair<int,int> > > g;
cin >> n;
p.resize(n);
r.resize(n);
vector<int> x(n),y(n);
for (int i=0;i<n;i++)
{
cin >> x[i] >> y[i];
make_set(i);
}
for (int i=0;i<n-1;i++)
for (int j=i+1;j<n;j++)
{
++m;
g.push_back(pair< float,pair<int,int> >(sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])),pair<int,int>(i,j)));
}
sort(g.begin(),g.end());
float dist=0;
for (int i=0;i<m;i++)
if (find_set(g[i].second.first)!=find_set(g[i].second.second))
{
dist+=g[i].first;
union_sets(g[i].second.first,g[i].second.second);
}
cout << ios::fixed << setprecision(2) << dist;
return 0;
} |
|
но он выдает неправильный ответ. Пожалуйста помогите исправить мой код
0
|
(
Сообщение от (SkyNet)
