acwing-347. 野餐规划

发表于 分类于 阅读次数： Waline： 本文字数： 2.1k 阅读时长 ≈ 7 分钟

考点

  • 最小生成树
  • flood-fill找连通块
  • 树形DP

题解

见思路

思路

给定一张N个点M条边的无向图，求出无向图的一颗最小生成树，满足1号节点（公园）的度数不超过给定的整数S

删边

最容易想到的办法就是模拟题意进行删边，由于题目没说无解的情况，那么1号节点的入度deg一定大于等于s

  1. 原图保存至邻接矩阵a，用prim算法求出最小生成树并保存至邻接矩阵tree

  2. 枚举tree中1号节点的所有出边，从中删除某一条(1, i)的同时，还需要从a中选一条新边加进tree以保证最小生成树的结构。

    设min_val = min_edge - tree[1][i]，min_edge是新增的边权，tree[1][i]是删除的边权，min_val称为增加程度，显然min_val尽可能小，那么新的最小生成树总权值就会尽可能小。

    对比删不同边的min_val，取最小值。

  3. tree删除边(1, i)后，整个生成树会变成两个连通块，v[1]和v[0]两种，假设删除边的另一点i所在连通块设为v[1]，那么1号节点（公园）也要放入v[1]。

  4. 遍历v[1]连通块的所有点（除了1号节点），是否与v[0]某个点有边，类似的边求权值最小即可得到min_edge。

  5. 回到2继续循环，直到出度deg不超过s

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 35;
int n, m, s, deg, ans, a[maxn][maxn], d[maxn];
bool v[maxn];
// tree：最小生成树的邻接矩阵
// conn[i]记录最小生成树的一条边(i, conn[i]），权值为d[i]
int tree[maxn][maxn], conn[maxn];

void read() {
  unordered_map<string, int> h;
  memset(a, 0x3f, sizeof(a));
  cin >> m;
  h["Park"] = 1, n = 1;
  string x, y;
  for (int z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    if (!h.count(x)) h[x] = ++n;
    if (!h.count(y)) h[y] = ++n;
    a[h[x]][h[y]] = a[h[y]][h[x]] = min(a[h[x]][h[y]], z);
  }
  cin >> s;
}

void prim() {
  memset(d, 0x3f, sizeof(d)), memset(v, 0, sizeof(v));
  d[1] = 0;
  for (int i = 1; i < n; ++i) {
    int x = 0;
    for (int j = 1; j <= n; ++j)
      if (!v[j] && (x == 0 || d[x] > d[j])) x = j;
    v[x] = 1;
    for (int y = 1; y <= n; ++y)
      if (!v[y] && d[y] > a[x][y]) {
        d[y] = a[x][y], conn[y] = x;
      }
  }
  memset(tree, 0x3f, sizeof(tree));
  for (int i = 2; i <= n; ++i) {
    ans += d[i];
    if (conn[i] == 1) ++deg;
    tree[conn[i]][i] = tree[i][conn[i]] = d[i];
  }
}

void dfs(int x) {
  v[x] = 1;
  for (int y = 2; y <= n; ++y)
    if (!v[y] && tree[x][y] != 0x3f3f3f3f) dfs(y);
}

// 能连接两个连通块的最小边
int find_min(int &x, int &y) {
  int min_edge = 0x3f3f3f3f, mix, miy;
  for (int i = 2; i <= n; ++i) {
    if (!v[i]) continue;
    for (int j = 2; j <= n; ++j) {
      if (v[j]) continue;
      if (a[i][j] != 0x3f3f3f3f && a[i][j] < min_edge) {
        min_edge = a[i][j];
        x = i, y = j;
      }
    }
  }
  return min_edge;
}

void solve() {
  // 减少的程度
  int min_val = 0x3f3f3f3f, mix, miy, mii;
  // 枚举最小生成树中1的所有出边
  for (int i = 2; i <= n; ++i) {
    if (tree[1][i] == 0x3f3f3f3f) continue;
    // 删除当前出边，最小生成树变成两个连通块，v[0]和v[1]两种
    memset(v, 0, sizeof(v));
    // 假设删除边的另一点所在连通块设为v[1]，那么公园要提前放入v[1]
    // 后续在两连通块之间寻找最小边时，可以避免v[1]连通块与公园相连
    v[1] = 1;
    dfs(i);
    int x, y;
    int min_edge = find_min(x, y);
    if (min_edge != 0x3f3f3f3f && min_edge - tree[1][i] < min_val) {
      min_val = min_edge - tree[1][i];
      mix = x, miy = y, mii = i;
    }
  }
  ans += min_val;
  tree[1][mii] = tree[mii][1] = 0x3f3f3f3f;
  tree[mix][miy] = tree[miy][mix] = a[miy][mix];
}

int main() {
  read();
  prim();
  while (deg > s) {
    solve();
    --deg;
  }
  cout << "Total miles driven: " << ans << endl;
  return 0;
}

加边

首先，去掉1号节点之后，无向图可能会分成若干个连通块。可以用深度优先遍历划分出图中的每个连通块，设连通块共有T个，若T > S，此题无解，因为每个连通块至少与1号节点有一条连边。

对于每个连通块，在这个连通块内部求出它的最小生成树，然后从连通块中选出一个节点p与1号节点相连，其中无向边(1, p)的权值尽量小。

此时已经得到了原无向图的一颗生成树，1号节点的度数为T，还有S - T个与1号节点的连边机会可以用于优化：

假设当前某连通块内的最小生成树有xu、uv两条边，连通块与1号节点的连边为1v，还有一条连边1x不选是因为权值比1v大。

找到点x到点1的所有最小生成树路径中，权值最大的边，即uv，而uv的权值是远大于1x的。

故而可以把uv去除，转而去连接1x，连通块内部的最小生成树就一拆为二，整体的最小生成树权值和也降低了。

每次遍历所有点，选择降低程度最大的那个即可，直到不能再优化或者机会用完。

可以使用树形DP提前打表，在生成树上求出每个点x到1号节点路径上权值最大的边(u, v)。

然而，如上图所示，每次选择新接入一个边(1, x)时，x所在的生成树会被拆分，

一个v为根的子树和一个以x为根的子树，前者所在的DP值不变，而后者需要重新DP一次。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <bits/stdc++.h>
using namespace std;
const int maxn = 35;
int n, m, s, deg, ans, p, a[maxn][maxn], d[maxn], ver[maxn];
bool v[maxn], c[maxn];
// tree：全图最小生成树
// conn[i]记录全图最小生成树的一条边(i, conn[i]），权值为d[i]
int tree[maxn][maxn], conn[maxn];
// (fx[i], fy[i])就是1~i路径上的最大边，边权是f[i]
int f[maxn], fx[maxn], fy[maxn];

void read() {
  cin >> m;
  map<string, int> h;
  h["Park"] = 1, n = 1;
  // 原图的邻接矩阵
  memset(a, 0x3f, sizeof(a));
  string x, y;
  for (int z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    if (!h.count(x)) h[x] = ++n;
    if (!h.count(y)) h[y] = ++n;
    a[h[x]][h[y]] = a[h[y]][h[x]] = min(a[h[x]][h[y]], z);
  }
  cin >> s;
}

void dfs(int x) {
  c[x] = 1;
  // 当前连通块有哪些点
  ver[++p] = x;
  for (int y = 1; y <= n; ++y) {
    if (c[y] || a[x][y] == 0x3f3f3f3f) continue;
    dfs(y);
  }
}

void prim(int root) {
  // 连通块内部找最小生成树
  d[root] = 0;
  for (int i = 1; i <= p; ++i) {
    int x = 0;
    for (int j = 1; j <= p; ++j) {
      if (!v[ver[j]] && (x == 0 || d[ver[j]] < d[x])) x = ver[j];
    }
    v[x] = 1;
    for (int j = 1; j <= p; ++j) {
      int y = ver[j];
      if (!v[y] && d[y] > a[x][y]) {
        d[y] = a[x][y], conn[y] = x;
      }
    }
  }
  // 选一条连通块到1节点的最短边加入到最小生成树中
  // 顺带把当前最小生成树合并到全图最小生成树
  int closest = root;
  for (int i = 1; i <= p; ++i) {
    int x = ver[i];
    if (x == root) continue;
    ans += d[x];
    tree[x][conn[x]] = tree[conn[x]][x] = d[x];
    if (a[1][x] < a[1][closest]) closest = x;
  }
  ++deg;
  ans += a[1][closest];
  tree[1][closest] = tree[closest][1] = a[1][closest];
}

void prim_for_all_comp() {
  memset(d, 0x3f, sizeof(d)), memset(v, 0, sizeof(v));
  memset(tree, 0x3f, sizeof(tree));
  c[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (!c[i]) {
      p = 0;
      // 寻找连通块
      dfs(i);
      // 对当前连通块内部执行prim
      prim(i);
    }
  }
}

// 树形dp打表，求x到1所有路径的最长边
void dp(int x) {
  v[x] = 1;
  for (int y = 2; y <= n; ++y) {
    if (!v[y] && tree[x][y] != 0x3f3f3f3f) {
      if (f[x] > tree[x][y]) {
        f[y] = f[x];
        fx[y] = fx[x], fy[y] = fy[x];
      } else {
        f[y] = tree[x][y];
        fx[y] = x, fy[y] = y;
      }
      dp(y);
    }
  }
  v[x] = 0;
}

bool solve() {
  // 记录改变的最小程度值
  int min_val = 1 << 30, mini;
  // 枚举所有的非全图最小生成树边(1,i)，看加哪一条
  for (int i = 2; i <= n; ++i) {
    if (tree[1][i] != 0x3f3f3f3f || a[1][i] == 0x3f3f3f3f) continue;
    // 加入非树边(1, i)，删去树边(fx[i], fy[i])
    if (a[1][i] - tree[fx[i]][fy[i]] < min_val) {
      min_val = a[1][i] - tree[fx[i]][fy[i]];
      mini = i;
    }
  }
  // 如果反而大了，说明不需要优化
  if (min_val >= 0) return 0;
  ans += min_val;
  tree[1][mini] = tree[mini][1] = a[1][mini];
  tree[fx[mini]][fy[mini]] = tree[fy[mini]][fx[mini]] = 0x3f3f3f3f;
  // 树断开一边后变成两个子树，所以要重新计算mini为根的子树dp状态
  f[mini] = a[1][mini];
  fx[mini] = 1, fy[mini] = mini;
  memset(v, 0, sizeof(v));
  v[1] = 1;
  dp(mini);
  return 1;
}

int main() {
  read();
  // 删掉1号点，分出若干个连通块，各自内部求prim
  prim_for_all_comp();
  memset(v, 0, sizeof(v));
  dp(1);
  while (deg < s) {
    if (!solve()) break;
    ++deg;
  }
  cout << "Total miles driven: " << ans << endl;
  return 0;
}