#3720. 网络优化
网络优化
题目描述
在一座城市中,有n个主要区域。为了促进经济发展,计划在这些区域之间建立一些直接的有向公路。每条公路都有一条单向路线,由主管部门拥有并维护。然而,并非所有可能的公路都是必要的,也不太可能在财务上盈利。因此,在进行公路网络规划时,必须仔细考虑。
输入格式
输入文件名为 input.txt。 第一行包含两个用空格分隔的整数n,m(1 ≤ n ≤ 100,0 ≤ m ≤ 10000)。 接下来的m行每行都包含三个用空格分隔的整数x,y,c(1 ≤ x,y ≤ n,x ≠ y,0 ≤ c ≤ 1000)。 这些整数的含义是,从区域x到区域y的公路的年维护成本为c欧元。可能有不止一条从区域x到区域y的公路。
输出格式
输出文件名为 output.txt。 第一行应包含可能的公路网络的最小维护成本。第二行为可能的公路网络的边列表。每条边都用三个空格分隔的整数组成,按升序排列的x,y和c,用英文分号分隔。如果可能的公路网络不成立,那么应写一行Impossible。
样例
3 4
1 2 1
2 3 1
1 3 2
3 1 3
4
3 1 3;
1 2 1;
4 4
1 2 1
2 3 1
1 3 2
3 1 3
Impossible
说明/提示
在任何有向图的生成树中,必须包含从根节点出发的边,这些边不能形成循环。 对于生成树中的每个区域,必须通过网络与根节点联系起来。
解析
题解
问题分析 题目要求我们从给定的有向图中选择一条生成树,使得维护成本之和最小。这显然是找到一个最小生成树(MST)的问题。由于生成树必须是连通的,并且每条边都按年维护成本排序,我们可以使用Krusky算法来解决这个问题。
解题思路
- Krusky算法:Krusky算法用于寻找图的最小生成树。该算法通过按边的权重(本题中为维护成本)从小到大排序,然后依次加入边,避免形成环路。这里使用并查集(Disjoint Set Union, DSU)来管理连通性。
- 输出检查:在构建好最小生成树后,需要检查是否所有的节点都连通。如果不能连通,则输出"Impossible"。否则,输出总成本和选中的边。
算法选择理由
- Krusky算法适用于边数较多的场景,时间复杂度O(m log m),适合本题m up to 1e4的情况。
- 并查集高效管理连通性,支持路径压缩和按秩合并,几乎常数时间级操作。
复杂度分析
- 时间复杂度:排序 edges O(m log m);Krusky算法O(m α(n)),其中α近似常数,总体O(m log m)。
- 空间复杂度:存储edges O(m + n),符合题面数据规模。
来源
AI 生成 · olympiccoder:7b · 省选/NOI- · 最小生成树