P5109: 修路方案-【2021暑期训练】T3Day2T3
【题目描述】
修路方案【问题描述】
戴将军率领着许多部队，它们分别驻扎在N个不同的城市里，这些城市分别编号1~N，由于交通不太便利，戴将军准备修路。
方斥候已经侦测到哪些城市之间可以修路，已经每条路的修建花费是多少。
现在，张军师已经找到了一种修路的最优方案，能够使各个城市都联通起来，而且花费最少。但是，戴将军认为这个修路方案所拼成的图案不够拉风，想让张军师计算一下另外一种方案，要求花费和刚才的方案相同或者尽量接近，
即min{新方案花费>=最优方案花费} 。
【文件输入】
输入文件warroad.in。
第一行是两个整数V,E，(3<V<500,10<E<200000)分别表示城市的个数和城市之间路的条数。数据保证所有的城市都有路相连。
随后的E行，每行有三个数字A,B和C，表示A号城市与B号城市之间修路花费为C。输入数据保证无重边。(0<a,b,c<maxlongint)。
【文件输出】
输出文件warroad.out。
一行一个整数，表示新方案的修建花费。
【输入样例】
5 6
1 2 2
1 3 3
2 3 4
2 4 5
3 4 1
3 5 3
【输出样例】
10
【样例输入】复制
【样例输出】 复制
【提示】
先看一个结论：次小生成树可由最小生成树换一条边得到，笔者认为很有必要搞清楚这一点，，否则对算法理解不够深入。
证明:咱换种方式去看待这个结论(一个生成树可以通过换边得到另一个生成树)，T是某一棵最小生成树，T0是任一棵异于T的生成树，通过变换T0 --> T1 --> T2 --> ... --> Tn (T) 变成最小生成树。所谓的变换是，每次把Ti中的某条边换成T中的一条边, 而且树T(i+1)的权小于等于Ti的权。
看下面的具体步骤(一定要理解透彻)。
step 1. 在Ti中任取一条不在T中的边uv.
step 2. 把边uv去掉，就剩下两个连通分量A和B，在T中，必有唯一的边u'v' 连结A和B。这是为什么呢？因为生成树中任意两点间只有一条路径(下面也要用这个)，且必有一条。
step 3. 显然u'v'的权比uv小 (prime算法贪心的，否则,uv就应该在T中)，把u'v'替换uv即得树T(i+1)。
特别地：取T0为任一棵次小生成树，T(n-1) 也就是次小生成树且跟T差一条边， 结论得证。
下面看具体算法。
step 1. 先用prim求出最小生成树T，在prim的同时，用一个矩阵maxd[u][v] 记录 在T中连结任意两点u,v的唯一的路中权值最大的那条边的权值.(有些拗口)，这是很容易做到的，因为prim是每次增加一个结点s, 在此需要保存节点和其父节点，采用DP，则最大权值要么是新加入的边，要么是父节点到起始点的采用DP算出来的距离，如下：
//u是刚加入的点，不过还没进入节点数组，v是已经存在的点//min是按prime新加入那条边maxd[v][u] = maxd[u][v] = max{min，maxd[father[u]][v]}
该步骤用时 O(V^2)，就是prime算法的耗时。
step 2. 枚举所有不在T中的边uv, 加入边uv则必然替换权为maxd[u][v]的边，这样才能保证次小。
二.算法实现
以POJ1679为例，判断最小生成树是否唯一(不唯一可能是重边，不过一般在做题里不可能，否则没法建图，另外就是一般情况了，看下图)。
下面这三个图都是MST，权值161。
只要最小生成树和次小生成树权值和一样就唯一。因此得出如下算法，首先计算出最小生成树T，然后对最小生成树上任意不相邻的两个点 uv添加最小生成树以外的存在的边形成环，然后寻找u与v之间最小生成树上最长的边删去，计算map[i][j]与 maxd[i][j差值，求出最小的来，如果是0，就说明MST和次小生成树一样。