Kruskal.

Table of Contents

  1. Description
  2. Solution

Description

给一个 $n$ 个点, $m$ 条边的无向图, 其中有一些是特殊边, 构造一颗生成树, 使得恰好包含 $k$ 条特殊边, 或输出无解.

Solution

考虑kruskal的过程, 假如我们优先假如非特殊边, 那么仍然需要使用的特殊边就一定会出现在最终方案中.

那么我们做两次kruskal就可以了.

注意判断一些诸如图不连通, 需要的特殊边过多, 可用的特殊边过少等情况.

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

using namespace std;

const int maxn = 2e+4 + 5;
const int maxm = 1e+5 + 5;

struct edge {
  int frm, to, typ;
  int tag;
  bool operator < (const edge &rhs){
    return typ > rhs.typ;
  }
}e[maxm];

int n, m, k;
int f[maxn];

int find(int x) {
  return (f[x] == x) ? x : f[x] = find(f[x]);
}
bool link(int x, int y) {
  int fx = find(x), fy = find(y);
  if (fx != fy) {
    f[fx] = fy;
    return true;
  }
  return false;
}
bool my_cmp(edge a, edge b) {
  return (a.tag == b.tag) ? a.typ < b.typ : a.tag > b.tag;
}

int main() {
  vector<int> vec;
  scanf("%d%d%d", &n, &m, &k); 
  int tmp = 0, ptr = 0;
  for (int i = 1; i <= n; ++i) 
    f[i] = i;
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &e[i].frm, &e[i].to, &e[i].typ);
  }
  sort(e + 1, e + 1 + m);
  for (int i = 1; i <= m; ++i) {
    if (!e[i].typ) ptr++;
    if (link(e[i].frm, e[i].to)) {
      if(!e[i].typ) tmp++, e[i].tag = 1;
    }
  }
  int cnt = 0;
  for (int i = 1; i <= n; ++i) {
    if (i == find(i)) cnt++;
  }
  if (ptr < k || tmp > k || cnt > 1) {
    puts("no solution");
  } else {
    sort(e + 1, e + 1 + m, my_cmp);
    for (int i = 1; i <= n; ++i) f[i] = i;
    int lim = 0;
    for (int i = 1; i <= m; ++i) {
      if (lim == k && e[i].typ == 0) continue;
      if (link(e[i].frm, e[i].to)) {
        vec.push_back(i);
        if (!e[i].typ) lim++;
      }
    }
    if (lim < k) {
      puts("no solution");
      return 0;
    }
    for (vector<int>::iterator i = vec.begin(); i != vec.end(); ++i) {
      printf("%d %d %d\n", e[*i].frm, e[*i].to, e[*i].typ);
    }
  }
  return 0;
}