思路：

提供一種題解區沒有的麻煩的要死的 LCT 做法。

轉換題意，求所有生成樹 P P P 的

M i n ( M a x i ∈ P g i × G + M a x i ∈ P s i × S ) Min(Max_{i\in P}\ g_i\times G+Max_{i\in P}\ s_i\times S) Min(Maxi∈P gi×G+Maxi∈P si×S)

發現和魔法森林很像。

考慮類似的維護方式。

化邊為點，先将邊按 g i g_i gi 排序，然後逐條加入邊，維護 s i s_i si 的最小生成樹，并在圖連通後每次更新答案。

考慮如何維護 s i s_i si 的最小生成樹：

加入一條邊：

如果邊的兩端點不連通，直接加入。
如果邊的兩端點連通，加入這條邊後勢必成環，找到環上 s i s_i si 最大的邊，删除即可。

于是 LCT 維護鍊的 M a x s i Max\ s_i Max si 即可。

考慮如何更新答案：

即要維護根節點的整棵子樹的 M a x g i Max\ g_i Max gi 和 M a x s i Max\ s_i Max si。

用 LCT 維護子樹最值的正常手段，在每個節點開一個 multiset 維護虛子樹的最值，在 access 和 link 時更新即可。

時間複雜度： O ( m l o g 2 ( n + m ) ) O(mlog^2(n+m)) O(mlog2(n+m)) （常數極大）。

于是可以加強到 n , m ≤ 1 0 5 n,m\leq 10^5 n,m≤105 。

注意最大的答案可能到 2 × 1 0 18 2\times 10^{18} 2×1018，于是 INF 要開大。

update:

經過奆佬 @FSYolanda 的提醒，更新答案隻用維護邊的集合，于是用一個 set 維護可以做到 O ( m l o g n ) O(mlogn) O(mlogn) (跑得挺快)。

于是可以加強到 n , m ≤ 1 0 6 n,m\leq 10^6 n,m≤106 了。

code：

O ( m l o g 2 ( n + m ) ) O(mlog^2(n+m)) O(mlog2(n+m))

#include <bits/stdc++.h>
using namespace std;

#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair

#define int long long

namespace IO {
char buf_[1 << 21], *p1_ = buf_, *p2_ = buf_;
#define ch()                                                                 \
  (p1_ == p2_ &&                                                             \
           (p2_ = (p1_ = buf_) + fread(buf_, 1, 1 << 21, stdin), p1_ == p2_) \
       ? EOF                                                                 \
       : *p1_++)
inline int in() {
  int s = 0, f = 1;
  char x = ch();
  for (; x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
char _buf[1 << 21];
int _pos = -1;
inline void flush() { fwrite(_buf, 1, _pos + 1, stdout), _pos = -1; }
inline void pc(char x) {
  if (_pos == (1 << 21) - 1) flush();
  _buf[++_pos] = x;
}
inline void out(int x) {
  char k[30];
  int pos = 0;
  if (!x) return pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) k[++pos] = (x % 10) | 48, x /= 10;
  for (re int i = pos; i; i--) pc(k[i]);
}
inline void out(string x) {
  int len = x.size();
  for (re int i = 0; i < len; ++i) pc(x[i]);
}
}  // namespace IO
using namespace IO;

const int A = 5e5 + 5;
const int INF = 3e18;
int n, m;
int G, S;
int ans = INF;

struct Road {
  int x, y, g, s;
  inline friend bool operator<(Road u, Road v) { return u.g < v.g; }
} p[A];

struct LCT {
  int ch[A][2], f[A], rev[A], mxg[A], mxs[A], xg[A], xs[A];
  struct MG {
    int x;
    MG(int _x = 0) { x = _x; }
    inline friend bool operator<(MG u, MG v) { return p[u.x].g > p[v.x].g; }
  };
  struct MS {
    int x;
    MS(int _x = 0) { x = _x; }
    inline friend bool operator<(MS u, MS v) { return p[u.x].s > p[v.x].s; }
  };
  multiset<MG> mg[A];
  multiset<MS> ms[A];

  inline int isroot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }

  inline int Maxg(int x, int y) { return p[x].g > p[y].g ? x : y; }
  inline int Maxs(int x, int y) { return p[x].s > p[y].s ? x : y; }

  inline void pushup(int x) {
    mxg[x] =
        Maxg(Maxg(x, (*mg[x].begin()).x), Maxg(mxg[ch[x][0]], mxg[ch[x][1]]));
    mxs[x] =
        Maxs(Maxs(x, (*ms[x].begin()).x), Maxs(mxs[ch[x][0]], mxs[ch[x][1]]));
    xg[x] = Maxg(x, Maxg(xg[ch[x][0]], xg[ch[x][1]]));
    xs[x] = Maxs(x, Maxs(xs[ch[x][0]], xs[ch[x][1]]));
  }

  inline void reverse(int x) {
    if (x) swap(ch[x][0], ch[x][1]), rev[x] ^= 1;
  }

  inline void pushdown(int x) {
    if (rev[x]) reverse(ch[x][0]), reverse(ch[x][1]), rev[x] ^= 1;
  }

  inline void rotate(int x) {
    int y = f[x], z = f[y];
    int k = (ch[y][1] == x);
    if (!isroot(y)) ch[z][(ch[z][1] == y)] = x;
    f[x] = z, ch[y][k] = ch[x][k ^ 1];
    if (ch[x][k ^ 1]) f[ch[x][k ^ 1]] = y;
    ch[x][k ^ 1] = y, f[y] = x;
    pushup(y);
    return;
  }

  int st[A], top;
  inline void pushpath(int x) {
    top = 0;
    st[++top] = x;
    for (int i = x; !isroot(i); i = f[i]) st[++top] = f[i];
    for (int i = top; i; i--) pushdown(st[i]);
    return;
  }

  inline void splay(int x) {
    pushpath(x);
    while (!isroot(x)) {
      int y = f[x], z = f[y];
      if (!isroot(y)) {
        if ((ch[y][1] == x) == (ch[z][1] == y))
          rotate(y);
        else
          rotate(x);
      }
      rotate(x);
    }
    pushup(x);
    return;
  }

  inline void access(int x) {
    for (int y = 0; x; y = x, x = f[x]) {
      splay(x);
      if (y) {
        mg[x].erase(mg[x].find(MG(mxg[y])));
        ms[x].erase(ms[x].find(MS(mxs[y])));
      }
      if (ch[x][1]) {
        mg[x].insert(MG(mxg[ch[x][1]]));
        ms[x].insert(MS(mxs[ch[x][1]]));
      }
      ch[x][1] = y;
      pushup(x);
    }
  }

  inline void makeroot(int x) { access(x), splay(x), reverse(x); }

  inline int findroot(int x) {
    access(x), splay(x);
    while (ch[x][0]) pushdown(x), x = ch[x][0];
    return x;
  }

  inline void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
  }

  inline void link(int x, int y) {
    makeroot(x);
    if (findroot(y) != x)
      f[x] = y, mg[y].insert(MG(mxg[x])), ms[y].insert(MS(mxs[x]));
    pushup(y);
  }

  inline void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && f[x] == y && ch[y][0] == x) f[x] = 0, ch[y][0] = 0;
    pushup(y);
  }

  struct DSU {
    int f[A], num[A];
    inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
    inline void merge(int x, int y) {
      if (find(x) != find(y))
        num[find(y)] += num[find(x)], f[find(x)] = find(y);
    }
  } D;

  inline void work(int now) {
    if (D.find(p[now].x) != D.find(p[now].y)) {
      link(p[now].x + m, now);
      link(p[now].y + m, now);
      D.merge(p[now].x, p[now].y);
    } else {
      split(p[now].x + m, p[now].y + m);
      if (p[xs[p[now].y + m]].s > p[now].s) {
        int t = xs[p[now].y + m];
        cut(p[t].x + m, t), cut(p[t].y + m, t);
        link(p[now].x + m, now), link(p[now].y + m, now);
      }
    }
    if (D.num[D.find(1)] == n) {
      makeroot(m + 1);
      ans = min(ans, p[mxg[m + 1]].g * G + p[mxs[m + 1]].s * S);
    }
    return;
  }

} T;

signed main() {
  n = in(), m = in(), G = in(), S = in();
  for (int i = 1; i <= m; i++)
    p[i].x = in(), p[i].y = in(), p[i].g = in(), p[i].s = in();
  sort(p + 1, p + 1 + m);
  for (int i = 1; i <= n; i++) T.D.f[i] = i, T.D.num[i] = 1;
  for (int i = 1; i <= m; i++) T.mxg[i] = T.mxs[i] = i;
  for (int i = 1; i <= m; i++) T.work(i);
  out(ans == INF ? -1 : ans), pc('\n');
  flush();
  return 0;
}

code:

O ( m l o g n ) O(mlogn) O(mlogn)

#include <bits/stdc++.h>
using namespace std;

#define re register
#define LL long long
typedef unsigned int uint;
typedef unsigned long long ull;
#define fir first
#define sec second
#define pb push_back
#define mp make_pair

#define int long long

namespace IO {
char buf_[1 << 21], *p1_ = buf_, *p2_ = buf_;
#define ch()                                                                 \
  (p1_ == p2_ &&                                                             \
           (p2_ = (p1_ = buf_) + fread(buf_, 1, 1 << 21, stdin), p1_ == p2_) \
       ? EOF                                                                 \
       : *p1_++)
inline int in() {
  int s = 0, f = 1;
  char x = ch();
  for (; x < '0' || x > '9'; x = ch())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = ch()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}
char _buf[1 << 21];
int _pos = -1;
inline void flush() { fwrite(_buf, 1, _pos + 1, stdout), _pos = -1; }
inline void pc(char x) {
  if (_pos == (1 << 21) - 1) flush();
  _buf[++_pos] = x;
}
inline void out(int x) {
  char k[30];
  int pos = 0;
  if (!x) return pc('0');
  if (x < 0) pc('-'), x = -x;
  while (x) k[++pos] = (x % 10) | 48, x /= 10;
  for (re int i = pos; i; i--) pc(k[i]);
}
inline void out(string x) {
  int len = x.size();
  for (re int i = 0; i < len; ++i) pc(x[i]);
}
}  // namespace IO
using namespace IO;

const int A = 5e5 + 5;
const int INF = 3e18;
int n, m;
int G, S;
int ans = INF;

struct Road {
  int x, y, g, s;
  inline friend bool operator<(Road u, Road v) { return u.g < v.g; }
} p[A];

struct LCT {
  int ch[A][2], f[A], rev[A], xg[A], xs[A];
  struct MG {
    int x;
    MG(int _x = 0) { x = _x; }
    inline friend bool operator<(MG u, MG v) { return p[u.x].g > p[v.x].g; }
  };
  struct MS {
    int x;
    MS(int _x = 0) { x = _x; }
    inline friend bool operator<(MS u, MS v) { return p[u.x].s > p[v.x].s; }
  };
  multiset<MG> mg;
  multiset<MS> ms;

  inline int isroot(int x) { return ch[f[x]][0] != x && ch[f[x]][1] != x; }

  inline int Maxg(int x, int y) { return p[x].g > p[y].g ? x : y; }
  inline int Maxs(int x, int y) { return p[x].s > p[y].s ? x : y; }

  inline void pushup(int x) {
    xg[x] = Maxg(x, Maxg(xg[ch[x][0]], xg[ch[x][1]]));
    xs[x] = Maxs(x, Maxs(xs[ch[x][0]], xs[ch[x][1]]));
  }

  inline void reverse(int x) {
    if (x) swap(ch[x][0], ch[x][1]), rev[x] ^= 1;
  }

  inline void pushdown(int x) {
    if (rev[x]) reverse(ch[x][0]), reverse(ch[x][1]), rev[x] ^= 1;
  }

  inline void rotate(int x) {
    int y = f[x], z = f[y];
    int k = (ch[y][1] == x);
    if (!isroot(y)) ch[z][(ch[z][1] == y)] = x;
    f[x] = z, ch[y][k] = ch[x][k ^ 1];
    if (ch[x][k ^ 1]) f[ch[x][k ^ 1]] = y;
    ch[x][k ^ 1] = y, f[y] = x;
    pushup(y);
    return;
  }

  int st[A], top;
  inline void pushpath(int x) {
    top = 0;
    st[++top] = x;
    for (int i = x; !isroot(i); i = f[i]) st[++top] = f[i];
    for (int i = top; i; i--) pushdown(st[i]);
    return;
  }

  inline void splay(int x) {
    pushpath(x);
    while (!isroot(x)) {
      int y = f[x], z = f[y];
      if (!isroot(y)) {
        if ((ch[y][1] == x) == (ch[z][1] == y))
          rotate(y);
        else
          rotate(x);
      }
      rotate(x);
    }
    pushup(x);
    return;
  }

  inline void access(int x) {
    for (int y = 0; x; y = x, x = f[x]) splay(x), ch[x][1] = y, pushup(x);
  }

  inline void makeroot(int x) { access(x), splay(x), reverse(x); }

  inline int findroot(int x) {
    access(x), splay(x);
    while (ch[x][0]) pushdown(x), x = ch[x][0];
    return x;
  }

  inline void split(int x, int y) {
    makeroot(x);
    access(y);
    splay(y);
  }

  inline void link(int x, int y) {
    makeroot(x);
    if (findroot(y) != x) f[x] = y;
  }

  inline void cut(int x, int y) {
    makeroot(x);
    if (findroot(y) == x && f[x] == y && ch[y][0] == x) f[x] = 0, ch[y][0] = 0;
    pushup(y);
  }

  struct DSU {
    int f[A], num[A];
    inline int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); }
    inline void merge(int x, int y) {
      if (find(x) != find(y))
        num[find(y)] += num[find(x)], f[find(x)] = find(y);
    }
  } D;

  inline void work(int now) {
    if (D.find(p[now].x) != D.find(p[now].y)) {
      link(p[now].x + m, now);
      link(p[now].y + m, now);
      mg.insert(MG(now)), ms.insert(MS(now));
      D.merge(p[now].x, p[now].y);
    } else {
      split(p[now].x + m, p[now].y + m);
      if (p[xs[p[now].y + m]].s > p[now].s) {
        int t = xs[p[now].y + m];
        cut(p[t].x + m, t), cut(p[t].y + m, t);
        mg.erase(mg.find(t)), ms.erase(ms.find(t));
        link(p[now].x + m, now), link(p[now].y + m, now);
        mg.insert(MG(now)), ms.insert(MS(now));
      }
    }
    if (D.num[D.find(1)] == n)
      ans = min(ans, p[(*mg.begin()).x].g * G + p[(*ms.begin()).x].s * S);
    return;
  }

} T;

signed main() {
  n = in(), m = in(), G = in(), S = in();
  for (int i = 1; i <= m; i++)
    p[i].x = in(), p[i].y = in(), p[i].g = in(), p[i].s = in();
  sort(p + 1, p + 1 + m);
  for (int i = 1; i <= n; i++) T.D.f[i] = i, T.D.num[i] = 1;
  for (int i = 1; i <= m; i++) T.work(i);
  out(ans == INF ? -1 : ans), pc('\n');
  flush();
  return 0;
}

題解 CF76A【Gift】思路：code：code:

思路：

code：

code:

繼續閱讀

貪心練習題

webAPI 第一天的相關習題

C++測試題：兩種排序方法标題：兩種排序方法

PTA練習題：一進制多項式的乘法與加法運算

2021.04.08遞歸實作斐波那契數列

20191030 練習：多源最短路

shell通過awk、sed提取指定内容、段落，練習題

Luogu P1967 貨車運輸

二叉搜尋樹得後序周遊序列(java)

機動車号牌查詢，線上查詢, api 查詢

Spring - 5 Spring架構整合JUnit單元測試

《黑馬程式員》 TreeSet集合練習之按照字元串長度排序

練習 - 寵物市場

UFLDL練習(Sparse Autoencoder)

Yandex.Algorithm Online Round 3 Sunday, June 15, 2014

集合練習題1