Select solution language
Write solution here.
### Nhận xét:
Mỗi vườn cây cần thuộc một thành phần liên thông, chứa ít nhất một giếng.
Để tối ưu thì trong mỗi thành phần liên thông đó, ta chỉ đào một giếng duy nhất.Vậy đồ thị có dạng nhiều thành phần liên thông, mỗi thành phần liên thông có một giếng duy nhất.
```
(5) (4) (9)
/ | \
/ | \
|.| |.| |.|
/ \ / | \ |
2 3 9 6 1 5
/ \ / | \ |
|.| |.| |.| |.| |.| |.|
.............|
.............5
.............|
............|.|
Note: |.| - vườn cây
(x): giếng với chi phí x
```
Có thể tưởng tượng việc đào giếng chính là tạo một cạnh giữa khu vườn $i$ với một đỉnh ảo $0$, với chi phí là $a[i]$. Ta cần tìm chi phí nhỏ nhất để tạo cây khung nhỏ nhất.
```
............... _ _ _|0|_ _ _
.............../ | \
............../ | \
............./ | \
............/ | \
/ | \
5 4 9
/ | \
/ | \
|.| |.| |.|
/ \ / | \ |
2 3 9 6 1 5
/ \ / | \ |
|.| |.| |.| |.| |.| |.|
.............|
.............5
.............|
............|.|
```
Code (C++17):
```cpp
#include<bits/stdc++.h>
#define el cout<<"\n"
#define maxn
using namespace std;
int n;
struct edge {
int u, v, w;
};
class dsu {
public:
vector<int> p;
int n;
dsu(int _n) : n(_n) {
p.resize(n+5);
iota(p.begin(), p.end(), 0);
}
inline int get(int x){return (x == p[x] ? x : (p[x] = get(p[x])));}
inline bool unite(int x, int y) {
x = get(x);
y = get(y);
if (x != y) {
p[x] = y;
return true;
}
return false;
}
};
main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n;
vector <edge> edges;
for (int i=1; i<=n; i++) {
int x; cin >> x;
edges.push_back({0, i, x});
}
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++) {
int x; cin >> x;
edges.push_back({i, j, x});
}
sort(edges.begin(), edges.end(), [] (edge e1, edge e2) {
return e1.w < e2.w;
});
dsu DSU(n);
int mst = 0;
for (auto [u, v, w] : edges) {
if (DSU.unite(u, v)) mst += w;
}
cout << mst;
}
```
YugiHacker
Created at
8 likes