1 条题解
-
0
#include <bits/stdc++.h> using namespace std; const int MAXN = 10000; const int MAXM = 20000; struct Edge { int u, v, w; }; Edge e[MAXM + 5]; int n, m, s, t; bool cmp(Edge a, Edge b) { return a.w < b.w; } int fa[MAXN + 5]; int cnt[MAXN + 5]; int findFa(int x) { if (fa[x] == x) return x; return fa[x] = findFa(fa[x]); } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> s >> t; if (s == t) { cout << 0; return 0; } for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w; // 并查集初始化 for (int i = 1; i <= n; i++) { fa[i] = i; cnt[i] = 1; } // kruskal 算法 sort(e + 1, e + m + 1, cmp); int sum = 0; for (int i = 1; i <= m; i++) { int u = e[i].u; int v = e[i].v; int w = e[i].w; int faU = findFa(u); int faV = findFa(v); if (faU != faV) { if (cnt[faU] < cnt[faV]) { fa[faU] = faV; cnt[faV] += cnt[faU]; } else { fa[faV] = faU; cnt[faU] += cnt[faV]; } if (findFa(s) == findFa(t)) { cout << w << "\n"; return 0; } } } return 0; }
信息
- ID
- 2201
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 3
- 标签
- 递交数
- 22
- 已通过
- 11
- 上传者