POJ 1797 条件最大生成树

发表于 分类于

这题做的囧死，看了样例很兴奋的写了个 dijkstra 交上去 WA，重新看了下题目，发现是每条路都有一个最大承载量，好吧，我又想错了，发现不是网络流，因为样例用最大流说不通，再仔细看了一遍题目，发现是叫你找一条路使得单条路的流量最大，果断写了个最大生成树，觉得最大生成树的最小边就是解，叫上去，再次 WA。

想了一会儿才发现不对，如果有一条路流量很大，但是这条路建出来的时候生成树没有建好呢？后来在 Kruskal 函数里加了一句很重要的话，果断 AC。。。。。

本题的思路就是求最大生成树，当 11 和 nn 在一个集合里的时候就返回最小边权，这个边权就是解。

我的代码：

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

using namespace std;

const int MAX = 1100;
const int oo = 0x3f3f3f3f;

struct Edge {
  int u, v, len;
  bool operator<(const Edge& e) const { return len > e.len; }
  void read() { scanf("%d%d%d", &u, &v, &len); }
} e[MAX * MAX];
int p[MAX], rank[MAX], n, m;

void init() {
  for (int i = 1; i <= n; i++) {
    p[i] = i;
    rank[i] = 0;
  }
}

int find(int x) { return p[x] = x == p[x] ? p[x] : find(p[x]); }

void Link(int x, int y) {
  if (rank[x] > rank[y]) {
    p[y] = x;
  } else {
    p[x] = y;
    if (rank[x] == rank[y]) {
      rank[y]++;
    }
  }
}

bool merge(int x, int y) {
  int px = find(x);
  int py = find(y);
  if (px == py) {
    return false;
  }
  Link(px, py);
  return true;
}

int Kruskal() {
  int ret = 0;
  int cnt = 1;
  init();
  sort(e, e + m);
  for (int i = 0; i < m && cnt < n; i++) {
    if (merge(e[i].u, e[i].v)) {
      cnt++;
      ret = e[i].len;
    }
    if (find(1) == find(n)) {
      break;
    }
  }
  return ret;
}

int main() {
  int t, cnt = 1;
  bool done = false;
  scanf("%d", &t);
  while (t--) {
    if (done) {
      puts("");
    } else {
      done = true;
    }
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
      e[i].read();
    }
    printf("Scenario #%d:\n", cnt++);
    printf("%d\n", Kruskal());
  }
  return 0;
}