2019.9.7 纪中模拟

一场远隔千里的模拟赛。


$Task$ 1

emm,考试的暴力打错了。不要在意这些细节。

根据 $Kruskal$ 的算法性质,可以得出,可能有很多不同的最小生成树,但是最小生成树的各个边一定是一一对应相同的。所以,可以说,只要确定了最小边,最大边是一定的。并且非常容易得出,最优解就是在这些生成树中。

所以说,枚举最小边,然后各跑一边 $Kruskal$ ,更新最优解。复杂度 $O(m^2)$

$Test’s$ $Code$:

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
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;
const int MAXN = 1e2 + 5;
const int MAXM = 1e4 + 5;
const int INF = 1 << 30;

int n, m, ans;

struct Edge {
int v, w, next;
};
Edge edge[MAXM];
int cnt, head[MAXN];

int flag[MAXN], fa[MAXN];

inline void Init () {
ans = INF + 100;
cnt = 0;
memset (head, 0, sizeof (head));
return;
}

inline void AddEdge (int u, int v, int w) {
cnt++;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt;
return;
}

void dfs (int u, int sum, int Min, int Max) {
if (Max - Min >= ans) return;

if (sum == n - 1) {
ans = min (Max - Min, ans);
return;
}

for (int i = head[u]; i != 0; i = edge[i].next) {
int v = edge[i].v;
int w = edge[i].w;

if (flag[v]) continue;

flag[v] = true;
dfs (v, sum + 1, min (Min, w), max (Max, w));
flag[v] = false;
}
return;
}

inline void solve () {
scanf ("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
fa[i] = i;
}
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf ("%d%d%d", &u, &v, &w);
AddEdge (u, v, w);
AddEdge (v, u, w);
}

dfs (1, 0, INF, -1);

printf ("%d\n", ans);
return;
}

int main() {
int tot;
scanf ("%d", &tot);

while (tot--) {
Init();
solve();
}
return 0;
}

$Fixed$ $Code$:

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
const int MAXN = 1e2 + 5;
const int MAXM = 1e4 + 5;
const int INF = 1 << 30;

struct Edge {
int u, v, w;
};
Edge edge[MAXM];

int n, m, ans, cnt;
int fa[MAXN];

inline void Init () {
ans = INF;
return;
}

bool cmp (Edge a, Edge b) {
return a.w < b.w;
}

int find (int x) {
if (x == fa[x]) return x;
return fa[x] = find (fa[x]);
}

inline void merge (int a, int b) {
int x = find (a);
int y = find (b);

fa[x] = y;
return;
}

inline void Kruskal (int l) {
cnt = 0;
for (int i = l; i <= m; i++) {
int u = edge[i].u;
int v = edge[i].v;

if (find(u) == find(v)) continue;
cnt++;
merge (u, v);

if (cnt >= n - 1) {
ans = min (ans, edge[i].w - edge[l].w);
return;
}
}

if (ans == INF) ans = -1;
return;
}

int main() {
int tot;
scanf ("%d", &tot);
while (tot--) {
Init ();

scanf ("%d%d", &n, &m);
if (m == 0) ans = -1;
for (int i = 1; i <= m; i++) {
scanf ("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
}

sort (edge + 1, edge + m + 1, cmp);

for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
fa[j] = j;
}
Kruskal (i);
if (ans == -1) break;
}

printf ("%d\n", ans);
}
return 0;
}

但是我发现了一个大问题,就是说,$O(m^2)$ 的复杂度比较高,只是因为数据水才跑的很快。而且非常容易想到一个方法:就是先一遍最小生成树,然后进一个吐一个,不是很方便吗??(这个思想可能有误)

于是,我找到了一篇更好的,复杂度为 $O(nm)$ 的 博文

溜了溜了。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×