# với bài toán này chúng ta không dùng thuật toán kruskal được vì chỉ tìm được chỉ 1 cây khung nhỏ nhất.
ví dụ:
```cpp
[1]
/ \
/ \
1 / \ 1
/ \
[2] ---- [3] ------ [4]
1 2
ta có:
4 4
1 2 1
1 3 1
2 3 1
3 4 2
nếu dùng kruskal đáp án sẽ là : 1101
```
thay vào đó dựa vào nền tảng tham lam của kruskal. chúng ta sẽ thử khả năng của các cạnh có
cùng trọng số theo thứ tự từ bé đến lớn.
phương pháp:
- b1 sort theo trọng số
- b2: sét và đánh dấu
- chúng ta sẽ có 2 lần sét các tập hợp cạnh chung trọng số
- lần thứ nhất, chỉ xem gốc của 2 đỉnh trên 1 cạnh, nếu par[u] != par[v] thì đỉnh đó có khả năng tạo một mst, và đánh dấu vào kết quả
- lần thứ hai , xét lại nhưng lần này chỉ gọi union_set(u, v) để đánh dấu gốc cho đỉnh
- lặp lại b2 đến khi hết toàn bộ cạnh của cây
## vì sao nó hoạt động?
```cpp
[1]
/ \
/ \
1 / \ 1
/ \
[2] ---- [3] ------ [4]
1 2
ta có:
4 4
1 2 1
1 3 1
2 3 1
3 4 2
```
với w0 = 1
lần xét thứ 1:
- par[1] != par[2] -> đánh dấu 1
- par[1] != par[3] -> đánh dấu 1
- par[2] != par[3] -> đánh dấu 1
- lần xét thứ 2;
- union_set(1, 2) thỏa mãng vì khác par
- union_set(1, 3) thỏa mãng vì khác par
- union_set(2, 3) thỏa mãng vì khác par
với w0 = 2
lần xét thứ 1:
- par[3] != par[4] -> đánh dấu 1
- lần xét thứ 2;
- union_set(3, 4) thỏa mãng vì khác par
```cpp
kết quả: 1111
```
code:
```cpp
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pll pair<ll, ll>
#define el "\n"
using namespace std;
struct Edge {
ll u, v, w, idx;
};
const ll MAXN = 1e5 + 5;
ll n, m, par[MAXN], sz[MAXN];
ll find_set(ll x) {
return (par[x] == x) ? x : par[x] = find_set(par[x]);
}
void union_set(ll a, ll b) {
a = find_set(a);
b = find_set(b);
if (a == b) return;
if (sz[a] < sz[b]) swap(a, b);
par[b] = a;
sz[a] += sz[b];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> m;
vector<Edge> Edges;
for (ll i = 0; i < m; i++) {
ll u, v, w;
cin >> u >> v >> w;
Edges.pb({u, v, w, i});
}
sort(Edges.begin(), Edges.end(), [](const Edge &A, const Edge &B) {
return A.w < B.w;
});
for (ll i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
}
vector <char> ans(m, '0');
ll i = 0;
// phần này quan trọng nhất
while(i < m) {
ll w0 = Edges[i].w;
ll j = i;
while(j < m && Edges[j].w == w0) j++;
for(int k = i; k < j; k++) {
auto [u, v, z, idx] = Edges[k];
ll ru = find_set(u);
ll rv = find_set(v);
if(ru != rv) ans[idx]++;
}
for(int k = i; k < j; k++) {
auto [u, v, z, idx] = Edges[k];
union_set(u, v);
}
i = j;
}
for (auto &x : ans) cout << x;
}
```
Long4200
Created at
3 likes