[luoguP2387] 魔法森林（LCT + 并查集）

并查集真是一个判断连通的好东西！

连通性用并查集来搞。

把每一条边按照 a 为关键字从小到大排序。

那么直接枚举，动态维护 b 的最小生成树

用 a[i] + 1 ~ n 路径上最大的 b[i] 更新答案即可

——代码

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #define N 200005

 #define get(x) (son[f[x]][1] == (x))

 #define min(x, y) ((x) < (y) ? (x) : (y))

 #define swap(x, y) ((x) ^= (y) ^= (x) ^= (y))

 #define isroot(x) (son[f[x]][0] ^ (x) && son[f[x]][1] ^ (x))

 int n, m, ans = ~( << );

 int mx[N], rev[N], fa[N], f[N], val[N], son[N][], s[N];

 struct node

 {

     int x, y, a, b;

 }e[N];

 inline int read()

 {

     int x = , f = ;

     char ch = getchar();

     for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;

     for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';

     return x * f;

 }

 inline bool cmp(node x, node y)

 {

     return x.a < y.a;

 }

 inline int getf(int x)

 {

     return x == fa[x] ? x : fa[x] = getf(fa[x]);

 }

 inline void update(int x)

 {

     if(x)

     {

         mx[x] = x;

         if(son[x][] && val[mx[son[x][]]] > val[mx[x]]) mx[x] = mx[son[x][]];

         if(son[x][] && val[mx[son[x][]]] > val[mx[x]]) mx[x] = mx[son[x][]];

     }

 }

 inline void pushdown(int x)

 {

     if(x && rev[x])

     {

         swap(son[x][], son[x][]);

         if(son[x][]) rev[son[x][]] ^= ;

         if(son[x][]) rev[son[x][]] ^= ;

         rev[x] = ;

     }

 }

 inline void rotate(int x)

 {

     int old = f[x], oldf = f[old], wh = get(x);

     if(!isroot(old))

         son[oldf][get(old)] = x;

     f[x] = oldf;

     son[old][wh] = son[x][wh ^ ];

     f[son[old][wh]] = old;

     son[x][wh ^ ] = old;

     f[old] = x;

     update(old);

     update(x);

 }

 inline void splay(int x)

 {

     int i, fat, t = ;

     s[++t] = x;

     for(i = x; !isroot(i); i = f[i]) s[++t] = f[i];

     for(i = t; i; i--) pushdown(s[i]);

     for(; !isroot(x); rotate(x))

         if(!isroot(fat = f[x]))

             rotate(get(x) ^ get(fat) ? x : fat);

 }

 inline void access(int x)

 {

     for(int t = ; x; t = x, x = f[x]) splay(x), son[x][] = t, update(x);

 }

 inline void reverse(int x)

 {

     access(x);

     splay(x);

     rev[x] ^= ;

 }

 inline void cut(int x, int y)

 {

     reverse(x);

     access(y);

     splay(y);

     son[y][] = f[x] = ;

     update(y);

 }

 inline void link(int x, int y)

 {

     reverse(x);

     f[x] = y;

     access(x);

 }

 inline int find(int x)

 {

     access(x);

     splay(x);

     while(son[x][]) x = son[x][];

     return x;

 }

 inline int query(int x, int y)

 {

     reverse(x);

     access(y);

     splay(y);

     return mx[y];

 }

 int main()

 {

     int i, j, k, x, y, a, b, t, fx, fy;

     n = read();

     m = read();

     for(i = ; i <= n; i++) fa[i] = i;

     for(i = ; i <= m; i++)

     {

         e[i].x = read();

         e[i].y = read();

         e[i].a = read();

         e[i].b = read();

         x = getf(e[i].x);

         y = getf(e[i].y);

         if(x ^ y) fa[x] = y;

     }

     if(getf() ^ getf(n))

     {

         puts("-1");

         return ;

     }

     std::sort(e + , e + m + , cmp);

     for(i = ; i <= m; i++)

     {

         mx[i + n] = i + n;

         val[i + n] = e[i].b;

     }

     for(i = ; i <= n; i++) fa[i] = i;

     for(i = ; i <= m; i++)

     {

         x = e[i].x;

         y = e[i].y;

         fx = getf(x);

         fy = getf(y);

         if(fx ^ fy)

         {

             link(x, i + n);

             link(y, i + n);

             fa[fx] = fy;

         }

         else

         {

             t = query(x, y);

             if(e[i].b < val[t])

             {

                 cut(e[t - n].x, t);

                 cut(e[t - n].y, t);

                 link(x, i + n);

                 link(y, i + n);

             }

         }

         if(getf() == getf(n)) ans = min(ans, e[i].a + val[query(, n)]);

     }

     printf("%d\n", ans);

     return ;

 }

排序很关键！

如果做不出来，先排序试试。

巴特西

[luoguP2387] 魔法森林（LCT + 并查集）

最新文章

热门文章