Это правильная реализация алгоритма Крускала?

Я написал следующий код в качестве решения проблемы UVA OnlineJudge # 10034:

// problem 10034

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

class tree;

class vertex {
public:
double x,y;
tree* mTree;
};

class tree {
public:
tree(tree* last,vertex* v);

int size();
void assimilate(tree* other);

tree* prev;
tree* next;
vector<vertex*> vertices;
};

tree::tree(tree* last,vertex* v) {
prev = last;
next = NULL;
vertices.push_back(v);
v->mTree = this;

if(last != NULL) {
last->next = this;
}
}

int tree::size() {
return vertices.size();
}

void tree::assimilate(tree* other) {
int c;

if(other->prev != NULL) {
other->prev->next = other->next;
}

if(other->next != NULL) {
other->next->prev = other->prev;
}

for(c = 0;c < other->vertices.size();c++) {
this->vertices.push_back(other->vertices[c]);

other->vertices[c]->mTree = this;
}

delete other;
}

class edge {
public:
edge() {
v1 = NULL;
v2 = NULL;
weight = 0;
}

edge(vertex* a,vertex* b,double w) {
v1 = a;
v2 = b;
weight = w;
}

bool operator<(const edge& rhs) const {
return this->weight < rhs.weight;
}

vertex* v1;
vertex* v2;
double weight;
};

double dist(double x1,double y1,double x2,double y2) {
double dx;
double dy;

dx = x2 - x1;
dy = y2 - y1;

return sqrt((dx*dx) + (dy*dy));
}

int main() {
int ncases;
int ccase;
int c;
int nverts;
int nedges;
edge* edges;
vertex* vertices;
tree* lasttree;
double cost;
tree* t1;
tree* t2;
bool treeexists;
int cedge;
int cc;cin>>ncases;

for(ccase = 0;ccase < ncases;ccase++) {
cin>>nverts;
nedges = (nverts*(nverts-1)) / 2;

treeexists = false;
lasttree = NULL;

vertices = new vertex[nverts];
edges = new edge[nedges];
cedge = 0;

for(c = 0;c < nverts;c++) {
cin>>vertices[c].x;
cin>>vertices[c].y;
lasttree = new tree(lasttree,&vertices[c]);
}

for(c = 0;c < nverts;c++) {
for(cc = c+1;cc < nverts;cc++) {
edges[cedge] = edge(vertices+c,vertices+cc,dist(vertices[c].x,vertices[c].y,vertices[cc].x,vertices[cc].y));
cedge++;
}
}

sort(edges,edges+nedges);

cost = 0;

for(c = 0;c < nedges;c++) {
//cout<<"edge with length "<<edges[c].weight<<endl;

if(edges[c].v1->mTree != edges[c].v2->mTree) {
//cout<<"using"<<endl;

cost += edges[c].weight;

t1 = edges[c].v1->mTree;
t2 = edges[c].v2->mTree;

if(t1->size() > t2->size()) {
t1->assimilate(t2);
} else {
t2->assimilate(t1);
}
}
}

if(ccase > 0) {
cout<<endl;
}

cout<<fixed<<setprecision(2)<<cost;

delete vertices[0].mTree;
delete[] vertices;
delete[] edges;
}

return 0;
}

Это работает как для тестового примера, предоставленного с проблемой, так и для более крупного тестового примера, который я нашел здесь: http://online-judge.uva.es/board/viewtopic.php?p=21939#p21939

Однако, когда я отправляю его в UVA, я получаю неверный ответ. Правильна ли моя реализация алгоритма Крукала? Что я делаю неправильно?

0

Решение

Во-первых, почему вы не используете структура данных поиска объединения вместо того, чтобы делать сложные манипуляции со структурой указателя?

Во-вторых, проблема, кажется, имеет неприятный трюк. Вы не хотите просто минимальное связующее дерево. Рассмотрим случай

4
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0

Мне нужно только 2 sqrt (2) единицы чернил, чтобы соединить все точки; Я делаю X из двух строк длиной sqrt (2). Однако минимальное остовное дерево имеет длину 3.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]