BZOJ3732 Network

news/2023/12/10 15:48:10

这貌似是13年的noip最后一道吧？、、、

蒟蒻只会这种题呢、、、

Kruskal求出MST，然后倍增就好了

  1 /**************************************************************
  2     Problem: 3732
  3     User: rausen
  4     Language: C++
  5     Result: Accepted
  6     Time:268 ms
  7     Memory:4412 kb
  8 ****************************************************************/
  9  
 10 #include <cstdio>
 11 #include <algorithm>
 12  
 13 using namespace std;
 14 const int N = 16005;
 15 const int M = 30005;
 16  
 17 struct Edge {
 18     int x, y, v;
 19      
 20     inline bool operator < (const Edge &x) const {
 21         return v < x.v;
 22     }
 23 } E[M];
 24  
 25 struct edge {
 26     int next, to, v;
 27     edge() {}
 28     edge(int _n, int _t, int _v) : next(_n), to(_t), v(_v) {}
 29 } e[M];
 30  
 31 struct tree_node {
 32     int fa[16], mx[16], dep;
 33 } tr[N];
 34  
 35 int n, m;
 36 int fa[N];
 37 int tot, first[N];
 38  
 39 inline int read() {
 40     int x = 0;
 41     char ch = getchar();
 42     while (ch < '0' || '9' < ch)
 43         ch = getchar();
 44     while ('0' <= ch && ch <= '9') {
 45         x = x * 10 + ch - '0';
 46         ch = getchar();
 47     }
 48     return x;
 49 }
 50  
 51 inline void Add_Edges(int x, int y, int v) {
 52     e[++tot] = edge(first[x], y, v), first[x] = tot;
 53     e[++tot] = edge(first[y], x, v), first[y] = tot;
 54 }
 55  
 56 int find_fa(int x) {
 57     return x == fa[x] ? x : fa[x] = find_fa(fa[x]);
 58 }
 59  
 60 void Kruskal() {
 61     int i, cnt, fa1, fa2;
 62     sort(E + 1, E + m + 1);
 63     for (i = 1; i <= n; ++i)
 64         fa[i] = i;
 65     for (i = 1, cnt = 0; i <= m; ++i) {
 66         fa1 = find_fa(E[i].x), fa2 = find_fa(E[i].y);
 67         if (fa1 != fa2) {
 68             fa[fa1] = fa2, ++cnt;
 69             Add_Edges(E[i].x, E[i].y, E[i].v);
 70             if (cnt == n - 1) break;
 71         }
 72     }
 73 }
 74  
 75 void dfs(int p) {
 76     int x, y;
 77     for (x = 1; x < 16; ++x) {
 78         tr[p].fa[x] = tr[tr[p].fa[x - 1]].fa[x - 1];
 79         tr[p].mx[x] = max(tr[p].mx[x - 1], tr[tr[p].fa[x - 1]].mx[x - 1]);
 80     }
 81     for (x = first[p]; x; x = e[x].next)
 82         if ((y = e[x].to) != tr[p].fa[0]) {
 83             tr[y].dep = tr[p].dep + 1;
 84             tr[y].fa[0] = p, tr[y].mx[0] = e[x].v;
 85             dfs(y);
 86         }
 87 }
 88  
 89 int query(int x, int y) {
 90     int res = 0, i;
 91     if (tr[x].dep < tr[y].dep) swap(x, y);
 92     for (i = 15; ~i; --i)
 93         if (tr[tr[x].fa[i]].dep >= tr[y].dep) {
 94             res = max(res, tr[x].mx[i]);
 95             x = tr[x].fa[i];
 96         }
 97     for (i = 15; ~i; --i)
 98         if (tr[x].fa[i] != tr[y].fa[i]) {
 99             res = max(res, max(tr[x].mx[i], tr[y].mx[i]));
100             x = tr[x].fa[i], y = tr[y].fa[i];
101         }
102     if (x != y)
103         res = max(res, max(tr[x].mx[0], tr[y].mx[0]));
104     return res;
105 }
106  
107 int main() {
108     n = read(), m = read();
109     int Q = read(), i, x, y;
110     for (i = 1; i <= m; ++i)
111         E[i].x = read(), E[i].y = read(), E[i].v = read();
112     Kruskal();
113     tr[1].dep = 1;
114     dfs(1);
115     while (Q--) {
116         x = read(), y = read();
117         printf("%d\n", query(x, y));
118     }
119     return 0;
120 }