「Solution」秘密的牛奶运输

Posted on Edited on In

题目连接

分析

一道可以暴力水过去的次小生成树

  • step1
    首先用$Kruskal$||$Prim$求出原图的一颗最小生成树，在连边的时候，用一个$vis$记录一下那些已经在最小生成树里面。
  • step2
    提前暴力$dfs$或者$bfs$求出任意两点构成的环之间的最大权值
    具体操作
    定义函数$dfs(int s, int u, int father, int mw1, int mw2)$
    s -> 起点 u -> 终点 father 判断是否回到原起点 mw1 最大值 mw2 次大值
    再用md1[s][u]保存从s -> u的最大边权值， 用md2[s][u]保存从s -> u的次大边权值
    循环遍历与重点u相连接的每一个点（v)，如果没有回到father就继续。
    定义t1, t2
    如果 从u -> v的 权值(w) 大于了现在的mw1
    - 把t1 更新为 w
- 把t2 更新为 mw1
    否则 如果 w 大于了现在的mw2 并且小于 mw1
    - 把t1 更新为 mw1
- 把t2 更新为 w
    最后递归遍历 dfs(s, v, u, t1, t2)
  • step2
    再一次考虑每一条非树边，用这条边上的权值考虑替换原边

    END

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <queue>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 505;
const int MAXM = 1e4 + 5;

long long n, m, tot, fa[MAXN], md1[MAXN][MAXN], md2[MAXN][MAXN];
long long ans, sum;
bool vis[MAXN];

struct node {
    long long u, v, w;
    bool vis;
} dis[MAXM];
bool cmp(node x, node y) {
    return x.w < y.w;
}

struct edge {
    int v, w;
    edge() {}
    edge(int V, int W) {
        v = V;
        w = W;
    }
};

vector<edge> G[MAXN];

void AddEdge(int u, int v, long long w) { G[u].push_back(edge(v, w)); }

int FindSet(int v) {
    if (fa[v] == v)
        return fa[v];
    else
        return fa[v] = FindSet(fa[v]);
}
bool UnionSet(int u, int v) {
    int x = FindSet(u);
    int y = FindSet(v);
    if (x == y)
        return 0;
    else {
        fa[x] = fa[y];
        return 1;
    }
}

void dfs(int s, int u, int fa, int mw1, int mw2) {
	md1[s][u] = mw1;
	md2[s][u] = mw2;
	for (int j = 0; j < G[u].size(); j++) {
		int v = G[u][j].v;
		int w = G[u][j].w;
		if (v != fa) {
			int t1, t2;
			if (w > mw1) {
				t1 = w;
				t2 = mw1;
			} else if (w < mw1 && w > mw2) {
				t1 = mw1;
				t2 = w;
			}
			dfs (s, v, u, t1, t2);
		}
	}
} 
void Kruskal() {
    for (int i = 1; i <= n; i++) fa[i] = i;
    sort(dis + 1, dis + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        if (UnionSet(dis[i].u, dis[i].v)) {
            sum += dis[i].w;
            tot++;
            dis[i].vis = 1;
            AddEdge(dis[i].u, dis[i].v, dis[i].w);
            AddEdge(dis[i].v, dis[i].u, dis[i].w);
        }
        if (tot == n - 1)
            break;
    }
    for (int i = 1; i <= n; i++) {
    	dfs (i, i, -1, 0, 0);
    }
    ans = 1e19;
    for (int i = 1; i <= m; i++) {
	if (dis[i].vis == 0) {
		int w = dis[i].w, u = dis[i].u, v = dis[i].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\n", ans);
}

int main() {
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf ("%lld %lld %lld", &dis[i].u, &dis[i].v, &dis[i].w);
    }
    Kruskal();
    return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」