beckerjc@150
|
1 |
#include <string>
|
beckerjc@150
|
2 |
#include <iostream>
|
beckerjc@150
|
3 |
#include <map>
|
beckerjc@150
|
4 |
|
beckerjc@150
|
5 |
#include <kruskal.h>
|
beckerjc@150
|
6 |
#include <list_graph.hh>
|
beckerjc@150
|
7 |
|
beckerjc@150
|
8 |
|
beckerjc@150
|
9 |
using namespace std;
|
beckerjc@150
|
10 |
using namespace hugo;
|
beckerjc@150
|
11 |
|
beckerjc@150
|
12 |
class string_int_map : public map<string,int> {
|
beckerjc@150
|
13 |
public:
|
beckerjc@150
|
14 |
int get(const string &s) {
|
beckerjc@150
|
15 |
// Bocs, ez igy gaaaany, de nem volt kedvem utananezni, hogy
|
beckerjc@150
|
16 |
// hogy is mukodik ez a map :)
|
beckerjc@150
|
17 |
if( count(s) == 0 ) {
|
beckerjc@150
|
18 |
operator[](s) = -1;
|
beckerjc@150
|
19 |
}
|
beckerjc@150
|
20 |
return operator[](s);
|
beckerjc@150
|
21 |
}
|
beckerjc@150
|
22 |
void set(const string &s, int i) {
|
beckerjc@150
|
23 |
operator[](s) = i;
|
beckerjc@150
|
24 |
}
|
beckerjc@150
|
25 |
};
|
beckerjc@150
|
26 |
|
beckerjc@150
|
27 |
|
beckerjc@150
|
28 |
int main() {
|
beckerjc@150
|
29 |
|
beckerjc@150
|
30 |
typedef ListGraph::NodeIt NodeIt;
|
beckerjc@150
|
31 |
typedef ListGraph::EdgeIt EdgeIt;
|
beckerjc@150
|
32 |
typedef ListGraph::EachNodeIt EachNodeIt;
|
beckerjc@150
|
33 |
typedef ListGraph::EachEdgeIt EachEdgeIt;
|
beckerjc@150
|
34 |
|
beckerjc@150
|
35 |
ListGraph G;
|
beckerjc@150
|
36 |
|
beckerjc@150
|
37 |
NodeIt s=G.addNode();
|
beckerjc@150
|
38 |
NodeIt v1=G.addNode();
|
beckerjc@150
|
39 |
NodeIt v2=G.addNode();
|
beckerjc@150
|
40 |
NodeIt v3=G.addNode();
|
beckerjc@150
|
41 |
NodeIt v4=G.addNode();
|
beckerjc@150
|
42 |
NodeIt t=G.addNode();
|
beckerjc@150
|
43 |
|
beckerjc@150
|
44 |
G.addEdge(s, v1);
|
beckerjc@150
|
45 |
G.addEdge(s, v2);
|
beckerjc@150
|
46 |
G.addEdge(v1, v2);
|
beckerjc@150
|
47 |
G.addEdge(v2, v1);
|
beckerjc@150
|
48 |
G.addEdge(v1, v3);
|
beckerjc@150
|
49 |
G.addEdge(v3, v2);
|
beckerjc@150
|
50 |
G.addEdge(v2, v4);
|
beckerjc@150
|
51 |
G.addEdge(v4, v3);
|
beckerjc@150
|
52 |
G.addEdge(v3, t);
|
beckerjc@150
|
53 |
G.addEdge(v4, t);
|
beckerjc@150
|
54 |
|
beckerjc@150
|
55 |
ListGraph::EdgeMap<double> edge_cost_map(G, 2);
|
beckerjc@150
|
56 |
ListGraph::EdgeMap<bool> tree_map(G);
|
beckerjc@150
|
57 |
|
beckerjc@150
|
58 |
double k0lts = MinCostTreeKruskal(G, edge_cost_map, tree_map);
|
beckerjc@150
|
59 |
|
beckerjc@150
|
60 |
cout << k0lts << endl;
|
beckerjc@150
|
61 |
|
beckerjc@150
|
62 |
return 0;
|
beckerjc@150
|
63 |
}
|