【洛谷P4234】最小差值生成树

亦凉 2023-06-05 08:53 39阅读 0赞

### Description ###

给定一张n个点，m条边的无向图，求出边权最大值和最小值差值最小的生成树

### Solution ###

LCT+并查集

按照最小生成树的思路，先将边按照边权从小到大排序，然后顺序考虑每一条边

如果当前这条边的两个端点没有连通，那么直接连通

如果两个端点已经连通，我们加上这条边会形成一个环，那么为了让“边权最大值和最小值差值”尽可能小，我们可以将这个环上最短的一条边删掉，换成这条边（显然是对的）

维护最小值可以通过LCT实现，连边、短边也是LCT的基本操作

当目前的边已经是一棵树的时候更新答案即可完成

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
      2 using namespace std;
      3 typedef long long ll;
      4 const int N = 50010;
      5 const int M = 200010;
      6 inline int read() {
      7     int ret = 0, op = 1;
      8     char c = getchar();
      9     while (!isdigit(c)) {
     10         if (c == '-') op = -1; 
     11         c = getchar();
     12     }
     13     while (isdigit(c)) {
     14         ret = (ret << 3) + (ret << 1) + c - '0';
     15         c = getchar();
     16     }
     17     return ret * op;
     18 }
     19 struct Edge {
     20     int from, to, dis;
     21     bool operator <(const Edge &x) const {
     22         return dis < x.dis;
     23     }
     24 } edge[M];
     25 struct LCT {
     26     int fa, val, minn, ch[2], tag;
     27 } a[N + M];
     28 int n, m, s[N + M], f[N];
     29 int vis[M];
     30 int find(int x) {
     31     if (f[x] != x) return f[x] = find(f[x]);
     32     return f[x];
     33 }
     34 inline int isnroot(int now) {
     35     return a[a[now].fa].ch[0] == now || a[a[now].fa].ch[1] == now;
     36 }
     37 inline int get(int x, int y) {
     38     return a[x].val < a[y].val ? x : y;
     39 }
     40 inline void update(int now) {
     41     int l = a[now].ch[0];
     42     int r = a[now].ch[1];
     43     a[now].minn = get(now, get(a[l].minn, a[r].minn));
     44 } 
     45 inline void rev(int now) {
     46     swap(a[now].ch[0], a[now].ch[1]);
     47     a[now].tag ^= 1;
     48 }
     49 inline void pushdown(int now) {
     50     if (a[now].tag) {
     51         if (a[now].ch[0]) rev(a[now].ch[0]);
     52         if (a[now].ch[1]) rev(a[now].ch[1]);
     53         a[now].tag = 0;
     54     }
     55 }
     56 void rotate(int x) {
     57     int y = a[x].fa;
     58     int z = a[y].fa;
     59     int xson = a[y].ch[1] == x;
     60     int yson = a[z].ch[1] == y;
     61     int B = a[x].ch[xson ^ 1];
     62     if (isnroot(y)) a[z].ch[yson] = x;
     63     a[x].ch[xson ^ 1] = y;
     64     a[y].ch[xson] = B;
     65     if (B) a[B].fa = y;
     66     a[y].fa = x;
     67     a[x].fa = z;
     68     update(y);
     69 }
     70 void splay(int x) {
     71     int y = x, z = 0;
     72     s[++z] = y;
     73     while (isnroot(y)) y = a[y].fa, s[++z] = y;
     74     while (z) pushdown(s[z--]);
     75     while (isnroot(x)) {
     76         y = a[x].fa;
     77         z = a[y].fa;
     78         if (isnroot(y))
     79             (a[z].ch[0] == y) ^ (a[y].ch[0] == x) ? rotate(x) : rotate(y);
     80         rotate(x);
     81     }
     82     update(x);
     83 }
     84 void access(int x) {
     85     for (register int y = 0; x; y = x, x = a[x].fa) {
     86         splay(x); a[x].ch[1] = y; update(x);
     87     }
     88 }
     89 void makeroot(int x) {
     90     access(x);
     91     splay(x);
     92     rev(x);
     93 }
     94 void link(int i) {
     95     makeroot(edge[i].from);
     96     a[edge[i].from].fa = i + N;
     97     a[i + N].fa = edge[i].to;
     98 }
     99 void cut(int i) {
    100     access(edge[i - N].from);
    101     splay(i);
    102     a[a[i].ch[1]].fa = a[a[i].ch[0]].fa = 0;
    103     a[i].ch[0] = a[i].ch[1] = 0;
    104 }
    105 int main() {
    106     n = read(); m = read();
    107     for (register int i = 0; i <= n; ++i) f[i] = i, a[i].val = 2147483647;
    108     for (register int i = 1; i <= m; ++i) {
    109         edge[i].from = read(); edge[i].to = read(); edge[i].dis = read();
    110     }
    111     sort(edge + 1, edge + m + 1);
    112     int sum = 0, ans = 0, k = 1;
    113     for (register int i = 1; i <= m; ++i) {
    114         a[i + N].val = edge[i].dis;
    115         int x = edge[i].from;
    116         int y = edge[i].to;
    117         if (find(x) != find(y)) {
    118             vis[i] = 1;
    119             sum++;
    120             link(i);
    121             f[f[x]] = f[y];
    122             if (sum == n - 1) ans = edge[i].dis - edge[k].dis;
    123         }
    124         else {
    125             if (x == y) continue ;
    126             vis[i] = 1;
    127             makeroot(x);
    128             access(y); splay(y);
    129             vis[a[y].minn - N] = 0;
    130             while (vis[k] == 0) ++k;
    131             cut(a[y].minn); link(i);
    132             if (sum == n - 1) ans = min(ans, edge[i].dis - edge[k].dis);
    133         }
    134     }
    135     printf("%d\n", ans);
    136     return 0;
    137 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11354557.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/645102bc847548278143dd53913ffe3c.png