Я написал следующий код в качестве решения проблемы 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, я получаю неверный ответ. Правильна ли моя реализация алгоритма Крукала? Что я делаю неправильно?
Во-первых, почему вы не используете структура данных поиска объединения вместо того, чтобы делать сложные манипуляции со структурой указателя?
Во-вторых, проблема, кажется, имеет неприятный трюк. Вы не хотите просто минимальное связующее дерево. Рассмотрим случай
4
0.0 0.0
1.0 0.0
1.0 1.0
0.0 1.0
Мне нужно только 2 sqrt (2) единицы чернил, чтобы соединить все точки; Я делаю X из двух строк длиной sqrt (2). Однако минимальное остовное дерево имеет длину 3.
Других решений пока нет …