每日算法题（Day4）----秘密的牛奶运输

题目描述

Farmer John 要把他的牛奶运输到各个销售点。运输过程中，可以先把牛奶运输到一些销售点，再由这些销售点分别运输到其他销售点。 运输的总距离越小，运输的成本也就越低。Farmer John 期望低成本的运输，但他并不想让他的竞争对手知道他具体的运输方案，所以他希望采用费用第二小的运输方案而不是最小的。现在请你帮忙找到该运输方案。

输入格式

第一行是两个整数 N,M，表示顶点数和边数；

接下来 M 行每行 33 个整数，x,y,z，表示一条路的两端 x,y 和距离 z。

输出格式

仅一行，输出第二小方案

分析

我的想法是暴力遍历，然后预置最短和次段路径迭代更新，然后成功TLE
大神的正确思路：
求次小生成树问题步骤：
1、求最小生成树，统计每条边是树边还是非树边，同时把最小生成树建出来。O(m)
2、预处理任意两点间的边权最大值dis[a][b]。O(n2) 用dfs或者bfs
3、依次枚举所有非树边，求min(sum+w-dis[a][b])，满足w>dis[a][b]，因为这个题是要严格次小生成树。

样例

4 4
1 2 100
2 4 200
2 3 250
3 4 100
------------------------
450

代码

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const  int N = 510, M = 10010;int f[N];
struct node 
{
    int x, y, dis;bool is_tree;bool operator<(const node& a) const{
    return dis < a.dis;}
}edge[M];
int n, m;
int dis[N][N], dis2[N][N];
int e[M], w[M], ne[M], h[N], len;void add(int a, int b, int c)
{
    e[len] = b;w[len] = c;ne[len] = h[a];h[a] = len++;
}void init()
{
    for (int i = 0; i < N; i++)f[i] = i;
}int find(int x)
{
    if (f[x] == x)return x;return f[x] = find(f[x]);
}void dfs(int u, int fa, int maxd1, int maxd2, int dis1[], int dis2[])
{
    dis1[u] = maxd1;dis2[u] = maxd2;for (int i = h[u]; ~i; i = ne[i]){
    int y = e[i];if (y != fa){
    // cout << u << " " << y << endl;int td1 = maxd1, td2 = maxd2;int c = w[i];if (c > maxd1)td2 = td1, td1 = c;else if (c < maxd1 && c > maxd2)td2 = c;dfs(y, u, td1, td2, dis1, dis2);}}
}int main()
{
    cin >> n >> m;init();for (int i = 1; i <= m; i++){
    int a, b, c;cin >> a >> b >> c;edge[i] = {
     a, b, c };}long long sum = 0;memset(h, -1, sizeof h);sort(edge + 1, edge + m + 1);for (int i = 1; i <= m; i++){
    int x = find(edge[i].x);int y = find(edge[i].y);if (x != y){
    int a = edge[i].x;int b = edge[i].y;int z = edge[i].dis;f[x] = y;add(a, b, z);add(b, a, z);edge[i].is_tree = true;sum += edge[i].dis;}else edge[i].is_tree = false;}for (int i = 1; i <= n; i++) dfs(i, -1, -1e9, -1e9, dis[i], dis2[i]);long long ans = 1e18;for (int i = 1; i <= m; i++){
    if (!edge[i].is_tree){
    int z = edge[i].dis;int a = edge[i].x;int b = edge[i].y;if (z > dis[a][b])ans = min(ans, sum - dis[a][b] + z);else if (z > dis2[a][b])ans = min(ans, sum - dis2[a][b] + z);}}cout << ans << endl;return 0;
}