8000 0x1B MST · HQVFX42/basic-algo-lecture@e756c2e · GitHub
[go: up one dir, main page]
Skip to content

Commit e756c2e

Browse files
encrypted-defencrypted-def
committed
0x1B MST
1 parent d052bf1 commit e756c2e

File tree

8 files changed

+310
-0
lines changed

8 files changed

+310
-0
lines changed

‎0x1B/1197_1.cpp

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
// http://boj.kr/aaafcfd71b164a75a8b89343bef17a46
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
vector<int> p(10005,-1);
6+
7+
int find(int x){
8+
if(p[x] < 0) return x;
9+
return p[x] = find(p[x]);
10+
}
11+
12+
bool is_diff_group(int u, int v){
13+
u = find(u); v = find(v);
14+
if(u == v) return 0;
15+
if(p[u] == p[v]) p[u]--;
16+
if(p[u] < p[v]) p[v] = u;
17+
else p[u] = v;
18+
return 1;
19+
}
20+
21+
int v, e;
22+
tuple<int,int,int> edge[100005];
23+
24+
int main(void) {
25+
ios::sync_with_stdio(0);
26+
cin.tie(0);
27+
28+
cin >> v >> e;
29+
for(int i = 0; i < e; i++){
30+
int a, b, cost;
31+
cin >> a >> b >> cost;
32+
edge[i] = {cost, a, b};
33+
}
34+
sort(edge, edge + e);
35+
int cnt = 0;
36+
int ans = 0;
37+
for(int i = 0; i < e; i++){
38+
int a, b, cost;
39+
tie(cost, a, b) = edge[i];
40+
if(!is_diff_group(a, b)) continue;
41+
ans += cost;
42+
cnt++;
43+
if(cnt == v-1) break;
44+
}
45+
cout << ans;
46+
}

‎0x1B/1197_2.cpp

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
// http://boj.kr/2af4791f2d2d416c88188b072a0157b7
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
#define X first
6+
#define Y second
7+
8+
int v, e;
9+
vector<pair<int,int>> adj[10005]; // {비용, 정점 번호}
10+
bool chk[10005]; // chk[i] : i번째 정점이 최소 신장 트리에 속해있는가?
11+
12+
int main(void) {
13+
ios::sync_with_stdio(0);
14+
cin.tie(0);
15+
16+
cin >> v >> e;
17+
for(int i = 0; i < e; i++){
18+
int a, b, cost;
19+
cin >> a >> b >> cost;
20+
adj[a].push_back({cost, b});
21+
adj[b].push_back({cost, a});
22+
}
23+
24+
int cnt = 0; // 현재 선택된 간선의 수
25+
int ans = 0;
26+
// tuple<int,int,int> : {비용, 정점 1, 정점 2}
27+
priority_queue< tuple<int,int,int>,
28+
vector<tuple<int,int,int>>,
29+
greater<tuple<int,int,int>> > pq;
30+
31+
chk[1] = 1;
32+
for(auto nxt : adj[1])
33+
pq.push({nxt.X, 1, nxt.Y});
34+
35+
while(cnt < v - 1){
36+
int cost, a, b;
37+
tie(cost, a, b) = pq.top(); pq.pop();
38+
if(chk[b]) continue;
39+
ans += cost;
40+
chk[b] = 1;
41+
cnt++;
42+
for(auto nxt : adj[b]){
43+
if(!chk[nxt.Y])
44+
pq.push({nxt.X, b, nxt.Y});
45+
}
46+
}
47+
cout << ans;
48+
}

‎0x1B/1368.cpp

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
// http://boj.kr/b794b88016994790b1d776f6cd14cb1f
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
vector<int> p(303,-1);
6+
7+
int find(int x){
8+
if(p[x] < 0) return x;
9+
return p[x] = find(p[x]);
10+
}
11+
12+
bool is_diff_group(int u, int v){
13+
u = find(u); v = find(v);
14+
if(u == v) return 0;
15+
if(p[u] == p[v]) p[u]--;
16+
if(p[u] < p[v]) p[v] = u;
17+
else p[u] = v;
18+
return 1;
19+
}
20+
21+
int v, e;
22+
tuple<int,int,int> edge[100005];
23+
24+
int main(void) {
25+
ios::sync_with_stdio(0);
26+
cin.tie(0);
27+
28+
cin >> v;
29+
// 가상의 v+1번째 정점과 연결
30+
for(int i = 1; i <= v; i++){
31+
int cost;
32+
cin >> cost;
33+
edge[e++] = {cost, i, v+1};
34+
}
35+
36+
for(int i = 1; i <= v; i++){
37+
for(int j = 1; j <= v; j++){
38+
int cost;
39+
cin >> cost;
40+
if(i >= j) continue;
41+
edge[e++] = {cost, i, j};
42+
}
43+
}
44+
v++; // 가상의 정점까지 포함해야 하므로 정점 수를 1 증가시킴
45+
sort(edge, edge + e);
46+
int cnt = 0;
47+
int ans = 0;
48+
for(int i = 0; i < e; i++){
49+
int a, b, cost;
50+
tie(cost, a, b) = edge[i];
51+
if(!is_diff_group(a, b)) continue;
52+
ans += cost;
53+
cnt++;
54+
if(cnt == v-1) break;
55+
}
56+
cout << ans;
57+
}

‎0x1B/solutions/1197.cpp

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/aaafcfd71b164a75a8b89343bef17a46
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
vector<int> p(10005,-1);
8+
9+
int find(int x){
10+
if(p[x] < 0) return x;
11+
return p[x] = find(p[x]);
12+
}
13+
14+
bool is_diff_group(int u, int v){
15+
u = find(u); v = find(v);
16+
if(u == v) return 0;
17+
if(p[u] == p[v]) p[u]--;
18+
if(p[u] < p[v]) p[v] = u;
19+
else p[u] = v;
20+
return 1;
21+
}
22+
23+
int v, e;
24+
tuple<int,int,int> edge[100005];
25+
26+
int main(void) {
27+
ios::sync_with_stdio(0);
28+
cin.tie(0);
29+
30+
cin >> v >> e;
31+
for(int i = 0; i < e; i++){
32+
int a, b, cost;
33+
cin >> a >> b >> cost;
34+
edge[i] = {cost, a, b};
35+
}
36+
sort(edge, edge + e);
37+
int cnt = 0;
38+
int ans = 0;
39+
for(int i = 0; i < e; i++){
40+
int a, b, cost;
41+
tie(cost, a, b) = edge[i];
42+
if(!is_diff_group(a, b)) continue;
43+
ans += cost;
44+
cnt++;
45+
if(cnt == v-1) break;
46+
}
47+
cout << ans;
48+
}

‎0x1B/solutions/1197_1.cpp

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/2af4791f2d2d416c88188b072a0157b7
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
#define X first
8+
#define Y second
9+
10+
int v, e;
11+
vector<pair<int,int>> adj[10005]; // {비용, 정점 번호}
12+
bool chk[10005]; // chk[i] : i번째 정점이 최소 신장 트리에 속해있는가?
13+
14+
int main(void) {
15+
ios::sync_with_stdio(0);
16+
cin.tie(0);
17+
18+
cin >> v >> e;
19+
for(int i = 0; i < e; i++){
20+
int a, b, cost;
21+
cin >> a >> b >> cost;
22+
adj[a].push_back({cost, b});
23+
adj[b].push_back({cost, a});
24+
}
25+
26+
int cnt = 0; // 현재 선택된 간선의 수
27+
int ans = 0;
28+
// tuple<int,int,int> : {비용, 정점 1, 정점 2}
29+
priority_queue< tuple<int,int,int>,
30+
vector<tuple<int,int,int>>,
31+
greater<tuple<int,int,int>> > pq;
32+
33+
chk[1] = 1;
34+
for(auto nxt : adj[1])
35+
pq.push({nxt.X, 1, nxt.Y});
36+
37+
while(cnt < v - 1){
38+
int cost, a, b;
39+
tie(cost, a, b) = pq.top(); pq.pop();
40+
if(chk[b]) continue;
41+
ans += cost;
42+
chk[b] = 1;
43+
cnt++;
44+
for(auto nxt : adj[b]){
45+
if(!chk[nxt.Y])
46+
pq.push({nxt.X, b, nxt.Y});
47+
}
48+
}
49+
cout << ans;
50+
}

‎0x1B/solutions/1368.cpp

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
// Authored by : BaaaaaaaaaaarkingDog
2+
// Co-authored by : -
3+
// http://boj.kr/b794b88016994790b1d776f6cd14cb1f
4+
#include <bits/stdc++.h>
5+
using namespace std;
6+
7+
vector<int> p(303,-1);
8+
9+
int find(int x){
10+
if(p[x] < 0) return x;
11+
return p[x] = find(p[x]);
12+
}
13+
14+
bool is_diff_group(int u, int v){
15+
u = find(u); v = find(v);
16+
if(u == v) return 0;
17+
if(p[u] == p[v]) p[u]--;
18+
if(p[u] < p[v]) p[v] = u;
19+
else p[u] = v;
20+
return 1;
21+
}
22+
23+
int v, e;
24+
tuple<int,int,int> edge[100005];
25+
26+
int main(void) {
27+
ios::sync_with_stdio(0);
28+
cin.tie(0);
29+
30+
cin >> v;
31+
// 가상의 v+1번째 정점과 연결
32+
for(int i = 1; i <= v; i++){
33+
int cost;
34+
cin >> cost;
35+
edge[e++] = {cost, i, v+1};
36+
}
37+
38+
for(int i = 1; i <= v; i++){
39+
for(int j = 1; j <= v; j++){
40+
int cost;
41+
cin >> cost;
42+
if(i >= j) continue;
43+
edge[e++] = {cost, i, j};
44+
}
45+
}
46+
v++; // 가상의 정점까지 포함해야 하므로 정점 수를 1 증가시킴
47+
sort(edge, edge + e);
48+
int cnt = 0;
49+
int ans = 0;
50+
for(int i = 0; i < e; i++){
51+
int a, b, cost;
52+
tie(cost, a, b) = edge[i];
53+
if(!is_diff_group(a, b)) continue;
54+
ans += cost;
55+
cnt++;
56+
if(cnt == v-1) break;
57+
}
58+
cout << ans;
59+
}

‎workbook/links.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,3 +25,4 @@
2525
0x18,그래프,https://www.acmicpc.net/workbook/view/9562
2626
0x19,트리,https://www.acmicpc.net/workbook/view/9657
2727
0x1A,위상 정렬,https://www.acmicpc.net/workbook/view/9738
28+
0x1B,최소 신장 트리,https://www.acmicpc.net/workbook/view/9907

‎workbook/problems.txt

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,3 +22,4 @@
2222
0x18,2606,1389,1707,5214
2323
0x19,4803,22856,20955,2533
2424
0x1A,2623,X,1766,2056
25+
0x1B,9372,X,13418,2887

0 commit comments

Comments
 (0)
0