P1879 - 简化农场 - New Online Judge

内存限制：256 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：34 通过：15

约翰的农场可以看做一个图，农田代表图中顶点，田间小路代表图中的边，每条边有一定的长度。
约翰发现自己的农场中最多有三条小路有着相同的长度。
约翰想删除一些小路使得农场成为一棵树，使得两块农田间只有一条路径。
约翰想把农场设计成最小生成树，也就是农场道路的总长度最短。
请帮助约翰找出最小生成树的总长度，同时请计算出总共有多少种最小生成树。

输入第一行为两个正整数 N 和 M ，表示点数和边数(1 <= N <= 40,000; 1 <= M <= 100,000)。
接下来 M 行，每行三个整数 ai, bi, ci，表示点 ai 和 bi 之间存在长度为 ci 的无向边。(1 <= ai, bi <= N; 1 <= ci <= 1,000,000)

输出一行包含两个整数，分别表示最小生成树的长度和最小生成树的数目。
数目对 1,000,000,007 求余.

4 3

来源：USACO 2011.12

进阶题最小生成树 USACO

1879: 简化农场

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签