BZOJ:https://www.lydsy.com/JudgeOnline/problem.php?id=1083
这题就是一道最小生成树的裸题
我使用的是 $ kruskal $ 算法。
题目的第一问就是 $ n - 1 $ ，这个是很显然的。
第二问就跑一下 $ kruskal $ 就行了。
$ code $
# include# include # include # include # include # define ll long long# define rg register# define il inlineusing namespace std;const int maxM = 300 * 300 + 10; struct Edge{ int frm; int to; int val;}edge[maxM];il void add_edge(int, int, int);il int kr();il bool cmp(Edge, Edge);int find(int);void join(int, int);int n, m, tot = 0, pre[maxM];int main(){ scanf("%d%d", &n, &m); for(rg int i = 1; i <= n; ++ i) pre[i] = i; for(rg int i = 0; i < m; ++ i) { rg int x, y, z; scanf("%d%d%d", &x, &y, &z); add_edge(x, y, z); } sort(edge, edge + tot, cmp); printf("%d %d", n - 1, kr());}il void add_edge(int x, int y, int z){ edge[tot].frm = x; edge[tot].to = y; edge[tot ++].val = z;}il bool cmp(Edge a, Edge b){ return a.val < b.val;}il int kr(){ rg int ans; for(rg int i = 0; i < m; ++ i) { rg int u = find(edge[i].frm); rg int v = find(edge[i].to); if(u != v) { join(u, v); ans = edge[i].val; } } return ans;}int find(int x){ if(x != pre[x]) pre[x] = find(pre[x]); return pre[x];}void join(int x, int y){ x = find(x), y = find(y); pre[x] = y;}