P3366 模板最小生成树
题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
样例解释：
因此，最小生成树的总边权是2 2 3=72 2 3=7。
P1546 [USACO3.1]最短网络 Agri-Net
题目背景
Farmer John 被选为他们镇的市长！他的竞选承诺之一是在镇上建立互联网，并连接到所有的农场。当然，他需要你的帮助。
题目描述
FJ 他已经为他的农场安排了一条高速网络线路，他想与其他农场分享。为了使用最小的消费，他想铺设最短的光纤来连接所有的农场。
你将得到每个农场之间的连接成本清单，你必须找到连接所有农场和最短光纤的方案。每两个农场之间的距离不会超过10^5105。
输入格式
第一行农场数量NN（3 \leq N \leq 1003≤N≤100）。
接下来是一个N \times NN×N矩阵表示每个农场之间的距离。理论上，他们是NN行，每行由NN实际上，由于每行空间分隔的数量组成8080因此，有些行会紧跟其他行。对角线当然会是00，因为没有线路从第一ii农场本身。
输出格式
只有一个输出，只有一个输出。
输入输出样例
复制
4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0
复制
28
说明/提示
题目翻译来自NOCOW。
USACO Training Section 3.1
P2330 [SCOI2005]繁忙的城市
题目描述
城市C是一个非常繁忙的大都市，城市里的道路非常拥挤，所以市长决定改造道路。城市C的道路分布如下：城市有n个交叉口，有些交叉口有道路连接，两个交叉口之间最多有一条道路连接。这些道路是双向的，所有的交叉口都是直接或间接的。每条路都有一个分数，分数越小，这条路越忙，越需要改造。但市政府资金有限，市长希望改造的道路越少越好，所以他提出了以下要求：
1.改造后的道路可以直接或间接连接所有交叉口。 2.在满足要求1的情况下，改造道路尽量少。 3.在满足1、2要求的情况下，改造道路中分数最大的道路分数应尽可能小。
任务:作为市规划局，你应该做出最好的决定，选择应该修建的道路。
输入格式
第一行有两个整数n,m说明城市有n个交叉口，m条道路。
接下来m行是对每条道路的描述，u, v, c表示交叉口u和v有道路相连，分值为c。(1≤n≤300，1≤c≤10000，1≤m≤100000)
输出格式
两个整数s, max，这意味着你选择了几条数最大的路的分数是多少。
输入输出样例
复制
4 5 1 2 3 1 4 5 2 4 7 2 3 6 3 4 8
复制
3 6
测试点信息
3ms/684.00KB
AC
#1
Accepted, 得分 10.ok accepted
6ms/680.00KB
AC
#2
Accepted, 得分 10.ok accepted
3ms/736.00KB
AC
#3
Accepted, 得分 10.ok accepted
3ms/688.00KB
AC
#4
Accepted, 得分 10.ok accepted
3ms/704.00KB
AC
#5
Accepted, 得分 10.ok accepted
4ms/808.00KB
AC
#6
Accepted, 得分 10.ok accepted
4ms/680.00KB
AC
#7
Accepted, 得分 10.ok accepted
4ms/808.00KB
AC
#8
Accepted, 得分 10.ok accepted
5ms/684.00KB
AC
#9
Accepted, 得分 10.ok accepted
6ms/724.00KB
AC
#10
Accepted, 得分 10.ok accepted
886，感谢阅读
谢了