题解 : https://xiaoxiaoh.blog.csdn.net/article/details/104227780
一、内容
秘密的牛奶运输
农夫约翰要把他的牛奶运输到各个销售点。
运输过程中,可以先把牛奶运输到一些销售点,再由这些销售点分别运输到其他销售点。
运输的总距离越小,运输的成本也就越低。
低成本的运输是农夫约翰所希望的。
不过,他并不想让他的竞争对手知道他具体的运输方案,所以他希望采用费用第二小的运输方案而不是最小的。
现在请你帮忙找到该运输方案。
注意::
如果两个方案至少有一条边不同,则我们认为是不同方案;
费用第二小的方案在数值上一定要严格小于费用最小的方案;
答案保证一定有解;
输入格式
第一行是两个整数 N,M,表示销售点数和交通线路数;
接下来 M 行每行 3 个整数 x,y,z,表示销售点 x 和销售点 y 之间存在线路,长度为 z。
输出格式
输出费用第二小的运输方案的运输总距离。
数据范围
1≤N≤500,
1≤M≤104,
1≤z≤109,
数据中可能包含重边。
输入样例:
4 4
1 2 100
2 4 200
2 3 250
3 4 100
输出样例:
450
二、思路
- 根据存在次小生成树与最小生成树只差一条边。
- 我们可以先通过kruskal求出最小生成树 O(mlogm)
- 通过这个树初始化某点到其他点的路径中最大边、次大边。 O(n^2^)
- 遍历所有未在树中的边(u–>v), 看是否大于u到v的边的最大值, 若大于那么可以替换这条边,若不大于那就再判断是否大于次值,若大于同理进行替换。
三、代码
#include <cstdio>
#include <algorithm>
typedef long long ll;
using namespace std;
const int N = 505, M = 1e4 + 5;
struct Edge {
int u, v, w;
bool in; //in代表这条边是否在树中
bool operator < (const Edge&o) const {
return w < o.w;
}
} edge[M];
struct E {
int v, w, next;
} e[N * 2]; //树的边有N-1条*双向
int n, m, len, h[N], md1[N][N], md2[N][N], p[N]; //md[i][j] 代表i到j点的路径上最大的一条边
int find(int x) { return x == p[x] ? x : (p[x] = find(p[x]));}
void add(int u, int v, int w) {
e[++len].v = v; e[len].w = w; e[len].next = h[u]; h[u] = len;
}
void dfs(int s, int u, int fa, int mw1, int mw2) {
//从s起点出发到其他点
md1[s][u] = mw1; md2[s][u] = mw2;
for (int j = h[u]; j; j = e[j].next) {
int v = e[j].v;
int w = e[j].w;
if (v != fa) {
int t1 = mw1, t2 = mw2;
if (w > mw1) t1 = w, t2 = mw1;
//这里不能相等
else if (w < mw1 && w > mw2) t2 = w;
dfs(s, v, u, t1, t2);
}
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) p[i] = i;
for (int i = 0; i < m; i++) scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
sort(edge, edge + m);
//求出最小生成树
ll sum = 0; //求出最小生成树的边权和
for (int i = 0; i < m; i++) {
int u = edge[i].u, v = edge[i].v , w = edge[i].w;
int fu = find(u), fv = find(v);
if (fu != fv) {
sum += w;
add(u, v, w); add(v, u, w); //构成树
edge[i].in = true; //代表在树中
p[fu] = fv;
}
}
//通过树 求出i到其他点的路径中的最大边
for (int i = 1; i <= n; i++) dfs(i, i, -1, 0, 0);
ll ans = 1e18;
for (int i = 0; i < m; i++) {
if (!edge[i].in) {
//如果这条边不在最小生成树中 考虑替换
int w = edge[i].w, u = edge[i].u, v = edge[i].v;
//如果这条边比u到v的路径中的最大边还大 那么可以替换 不然替换了反而变小
if (w > md1[u][v]) ans = min(ans, sum + w - md1[u][v]);
//如果和最大的边相等 那么判断是否大于次大边
else if (w > md2[u][v]) ans = min(ans, sum + w - md2[u][v]);
}
}
printf("%lld", ans);
return 0;
}
看了你的代码发现有一个问题,就是如果a点到b点的路径上所有的边权都相等,那么md2[a][b]一直都没被更新过,一直为0,针对这个漏洞我编了一个测试数据你可以试跑一下
Input
4 5
1 2 5
2 3 5
3 4 5
1 3 5
1 4 20
Output
30
(已加强测试数据)
只需要特判一下就行了,将下面这行代码
else if (w > md2[u][v]) ans = min(ans, sum + w - md2[u][v]);
改为下面这行
else if (w > md2[u][v] && md2[u][v]) ans = min(ans, sum + w - md2[u][v]);
就可以过了
我觉得你这样更合理,y总是把次小,未更新时变成-1e9了。
dist[a][a]的初始化不能为0, 应该为-INF, 否则当有自环的时候可能更新 (最小生成树和 + 自环权重 - 0),这显然不是一个生成树
最小生成树不是不能有自环吗
这个自环是除最小生成树之外的边?
想问一下为什么w会小于次大边,若一条边不在最小生成树中,那这条边不是一定大于等于最大边的吗
我主要是不明白为什么这个else后面还要加个if的判断,请大佬们不吝赐教
因为如果一条非树边等于最大边的时候,应该和次大边替换才能得到严格次小生成树
大佬,想问下dfs这里是怎么实现的呀
枚举每个点i为根出发,找出i到所有点j的最长边m1和严格次长边m2。但m1,m2只是有资格参评整个最小生成树中的最长边和严格次长边,并不一定就是最终的结果。我们还需要不断的变换根,这样,多次dfs枚举后,不断取最小,就保证了最终的d1[i][j],d2[i][j]中保存的就是终极答案最长边和严格次长边。
dfs这种方式很笨,但是有效,可以理解为是一种枚举办法,把所有情况都讨论到,那么最终的答案一定要讨论的范围内。
我的那里错了
那里错了
x,y的值,在做并查集检查时被覆盖了,而下面还要使用原始的 x,y值进行运算,保险的办法是多声明出px,py来防止变量被修改后再使用。
次小生成树与最小生成树一定只差一条边吗
对的,因为kruskal算法初始时是所有的点都不连通, 然后每次都看权值最小的边是不是在同一个连通块中,如果不是,就将他们连接起来。 如果一个图是连通图,通过这样可以构成最小生成树。那么我们如何构造出次小生成树呢?我们原来求最小生成树使用a边(图中将这两个不联通的点连通的最短的边)。但是求次小生成树时,我用一条比a边大的边连接这两个不联通的点, 其它的连接方式不变,这样可以构造出与原来不同的树。
求最小生成树时每条边都是最小值, 所以求次小生成树时,我们替换的边应该尽可能的少,最少就是要替换一条边,这棵树才和原来不一样。这个是一定存在的。
谢谢哥
我们也可以用逆向思维,把从次小生成树修复为最小生成树,可以发现次小生成树每修复一条边,整棵树的边权之和就会减小。而我们的修复次数就是次小生成树与最小生成树的边数差,若能二者差的边数不止一条边,我们就可以进行超过1次的修复操作,这样的话就会存在不是最小生成树,却比次小生成树还要小的树,这样就说明我们本来的次小生成树不满足条件。因此只要只差一条边时,才能作为次小生成树
dfs中这句代码错了 else if (w < mw1 && w > mw2) t2 = w;
改成 else if (mw1==mw2||w > mw2) t2 = w;
dl 您的代码好像是错的
$确实$