峰狂算法

发表于 分类于 Waline： 本文字数： 336 阅读时长 ≈ 1 分钟

性质

  • 多条直径必相交于一点或一条公共路径。

  • 任意两个同一侧的直径端点到相同直径分叉点的距离均相等。

  • 直径一定是最长边。

模板

两次BFS

边权均非负的情况才可以用，用于记录整条直径。

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
// 找到以bg为起点的直径
int bfs(int bg) {
  queue<int> q;
  memset(d, -1, sizeof(d));
  d[bg] = 0, q.push(bg);
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int y = ver[i];
      if (~d[y]) continue;
      q.push(y);
      d[y] = d[x] + edge[i];
      id[y] = i;
    }
  }
  int ed = bg;
  for (int i = 1; i <= n; ++i) {
    if (d[i] > d[ed]) ed = i;
  }
  return ed;
}

// 记录p为起点，q为终点的直径，从终点q逆推至p
// 每次记录第t个点到a，第t+1个点到b，所以最后要把起点p单独记录一次
void route(int p, int q) {
  while (q != p) {
    a[++t] = q;
    b[t + 1] = edge[id[q]];
    q = ver[id[q] ^ 1];
  }
  a[++t] = p;
}

树形DP

没有边权的正负限制，但只能保存直径的长度。

1
2
3
4
5
6
7
8
9
10
void dp(int x) {
  v[x] = 1;
  for (int i = head[x]; i; i = nxt[i]) {
    int y = ver[i];
    if (v[y]) continue;
    dp(y);
    l2 = max(l2, d[x] + d[y] + edge[i]);
    d[x] = max(d[x], d[y] + edge[i]);
  }
}

练习

发表于 更新于 分类于 Waline： 本文字数： 424 阅读时长 ≈ 1 分钟

模板

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 50, maxm = 2e5 + 50;
int n, m, ans, cnt, fa[maxn];

struct node {
  int x_, y_, z_;
  bool operator<(const node &a) const { return z_ < a.z_; }
} e[maxm];

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

void kruskal() {
  sort(e + 1, e + 1 + m);
  for (int x, y, i = 1; i <= m; ++i) {
    x = find(e[i].x_), y = find(e[i].y_);
    if (x != y) {
      ++cnt, ans += e[i].z_, fa[x] = y;
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) fa[i] = i;
  for (int x, y, z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    e[i] = {x, y, z};
  }
  kruskal();
  // 若连通，最小生成树只有n-1条边
  if (cnt == n - 1)
    cout << ans << endl;
  else
    cout << "orz" << endl;
  return 0;
}

Prim

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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 50, maxm = 2e5 + 50;
int n, m, ans, cnt, a[maxn][maxn], d[maxn], v[maxn];

void prim() {
  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[j] < d[x])) 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];
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (d[i] == 0x3f3f3f3f) {
      cout << "orz" << endl;
      return;
    }
    ans += d[i];
  }
  cout << ans << endl;
}

int main() {
  cin >> n >> m;
  memset(a, 0x3f, sizeof(a)), memset(d, 0x3f, sizeof(d));
  for (int x, y, z, i = 1; i <= m; ++i) {
    cin >> x >> y >> z;
    a[x][y] = a[y][x] = min(a[x][y], z);
  }
  prim();
  return 0;
}

核心

以最小的代价，让集合内部连通

Kruskal更倾向以集合的方式建模，Prim则更方便地记录最小生成树

练习题

0%