-
Notifications
You must be signed in to change notification settings - Fork 0
/
project1
129 lines (123 loc) · 2.29 KB
/
project1
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include<bits/stdc++.h>
uisng namespace std;
struct DSU{
vector<int> fa;
DSU(int n) : fa(n + 1) {
for(int i = 1;i <= n;i++)
fa[i] = i;
}
int find(int x){
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x,int y){
fa[x] = y;
}
};
struct Edge{
int a,b,v;
friend bool operator < (const Edge &a,const Edge &b){
return a.v < b.v;
}
};
struct Kruskal{
int n;
int m;
vector<Edge> e;
int ans;
void input(){
ans = 0;
puts("Please enter the number of points and edges n,m:");
cin >> n >> m;
puts("Please enter m edges which represents an edge between a and b the weight is v: a b v ");
for(int i = 0;i < m;i++){
int a,b,v;
cin >> a >> b >> v;
e.push_back({a,b,v});
}
}
void run(){
input();
DSU dsu(n);
sort(e.begin(),e.end());
int cnt = 0;
for(auto it = e.begin();it != e.end();it++){
int a = it -> a;
int b = it -> b;
if(dsu.find(a) != dsu.find(b)) {
ans += it -> v;
dsu.merge(a,b);
cnt++;
}
if(cnt == n - 1) break;
}
cout << "tot value = " << ans << '\n';
}
};
struct Prim{
int n;
int m;
vector<vector<pair<int,int>>> e;
vector<bool> vis;
vector<int> dis;
int ans;
void input(){
ans = 0;
puts("Please enter the number of points and edges n,m:");
cin >> n >> m;
e.resize(n + 1);
dis.resize(n + 1);
vis.resize(n + 1,0);
puts("Please enter m edges which represents an edge between a and b the weight is v: a b v ");
for(int i = 0;i < m;i++){
int a,b,v;
cin >> a >> b >> v;
e[a].push_back(make_pair(b,v));
e[b].push_back(make_pair(a,v));
}
}
void run(){
input();
int s = 1;
dis[s] = 0;
for(int i = 2;i <= n;i++)
dis[i] = INT_MAX;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
q.push(make_pair(0,1));
for(int i = 1;i <= n;i++){
q.push(make_pair(dis[i],i));
}
int cnt = 0;
while(!q.empty() && cnt < n){
auto u = q.top();
q.pop();
if(vis[u.second]) continue;
vis[u.second] = 1;
cnt++;
ans += u.first;
for(auto v:e[u.second]) {
if(v.second < dis[v.first]) dis[v.first] =v.second,q.push(make_pair(dis[v.first],v.first));
}
}
cout << "tot value = " << ans << '\n';
}
};
int main(){
Kruskal test1;
test1.run();
Prim test2;
test2.run();
}
/*
6 10
1 2 6
1 4 5
1 3 1
2 3 5
3 4 5
2 5 3
3 5 6
3 6 4
5 6 6
4 6 2
Expected:15
*/