题目链接： 传送门
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; //注意开的范围 const int N = 600010; int p[N], n, m, ans, ca = 1; //开一个边的结构体 struct edge { int s, e, val; }edges[N]; //排序函数 bool cmp(edge a,edge b) { return a.val > b.val; } //找到根节点 int find(int x) { if(p[x] == x) return x; return p[x] = find(p[x]); } //连接两个结点 void merge(int x,int y) { p[find(x)]= find(y); } int main() { int t; scanf("%d",&t); while(t--) { ans = 0; scanf("%d%d", &n, &m); //初始化父结点 for(int i = 1; i <= n; i++) p[i] = i; for(int i = 1; i <= m; i++) scanf("%d%d%d", &edges[i].s, &edges[i].e, &edges[i].val); //对边权进行排序（大的优先排前面） sort(edges + 1,edges + m + 1, cmp); for(int i = 1; i <= m; i++) { edge cur = edges[i]; //判断两点是否连接，未连接则连接，连接则跳过 if(find(cur.s) != find(cur.e)) merge(cur.s,cur.e); //判断起点与终点是否已经连接在了一起，是则跳出 if(find(1) == find(n)) { ans = cur.val; break; } } //输出结果，一定要注意格式 printf("Scenario #%d:\n", ca++); printf("%d\n\n", ans); } }这道题我是用卡鲁索算法的思想来做的，与传统的卡鲁索算法求最小生成树有一点区别，这里要求的是最大的情况。 先讲讲卡鲁索算法的思路，就是先把一些边存下来，然后根据个边的权值进行排序（传统的卡鲁索是小权值排前，这道题要大权值排前），然后从头往后遍历，每次取当前边，判断这条边的起点与终点是否已经连接了起来，如果没连接则直接起来（如果要求最小生成树的各路径总权值，则每次要把这个边的边权加入答案中），连接了则跳过。然后判断起点与终点是否已经连接成功，成功则跳出，未成功就继续。
