CF76A Gift 题解
题目链接：CF76A Gift
题意：
一张 \(N\) 个点 \(M\) 条边的无向图，每条边有两个属性 \((g_i, s_i)\)。
给定 \(G, S\)，求一棵图的生成树 \(T\)，使得 \(G \times \max(g_i) + S \times \max (s_i)\) 最小。（\(i\in T\)）
注意：图可能包含重边和自环。
数据范围：
\(2 \le N \le 200,~1\le M \le 50000,~1 \le G,S \le 10^9\) 。
考虑将边化成点，然后按 \(g_i\) 排序，依次加入每条边，
同时维护 \(s_i\) 的最小生成树，每次图连通时更新答案。
维护 \(s_i\) 的最小生成树时，如果两个点不连通直接合并，否则我们需要找到所成环上的 \(s_i\) 最大值。
考虑用 LCT 维护链上的 \(s_i\) 最大值即可。更新答案的话，可以开两个 multiset 维护边集。
时间复杂度 \(\mathcal{O}(m \log n)\) ，轻松通过本题。
代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))
int n, m, G, S, res = INF;
struct Edge {int u, v, g, s; } e[N];
bool operator<(const Edge& a, const Edge& b) { return a.g < b.g; }
namespace LCT
{
struct node
{
int ch[2], num, fa, ansg, anss, tag;
}t[N];
struct MG { int x; };
bool operator<(const MG& u, const MG& v) { return e[u.x].g > e[v.x].g; }
struct MS { int x; };
bool operator<(const MS& u, const MS& v) { return e[u.x].s > e[v.x].s; }
multiset<MG> mg; multiset<MS> ms;
struct dsu
{
int f[N], sz[N];
void init(int n) { rep(i, 1, n) { f[i] = i, sz[i] = 1; }}
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
void merge(int u, int v)
{
int x = find(u), y = find(v);
if(sz[x] > sz[y]) swap(x, y); sz[y] += sz[x]; f[x] = y;
}
}D;
#define isroot(x) ((t[t[x].fa].ch[0] != x)&&(t[t[x].fa].ch[1] != x))
void pushr(int x)
{
swap(t[x].ch[0], t[x].ch[1]);
t[x].tag ^= 1;
}
int Maxg(int x, int y) { return e[x].g > e[y].g ? x : y; }
int Maxs(int x, int y) { return e[x].s > e[y].s ? x : y; }
void push_up(int at)
{
t[at].ansg = Maxg(at, Maxg(t[t[at].ch[0]].ansg, t[t[at].ch[1]].ansg));
t[at].anss = Maxs(at, Maxs(t[t[at].ch[0]].anss, t[t[at].ch[1]].anss));
}
void push_down(int x)
{
if(t[x].tag)
{
if(t[x].ch[0]) pushr(t[x].ch[0]);
if(t[x].ch[1]) pushr(t[x].ch[1]);
t[x].tag = 0;
}
}
void push_all(int x)
{
if(!isroot(x)) push_all(t[x].fa);
push_down(x);
}
void rotate(int x)
{
int y = t[x].fa;
int z = t[y].fa;
int k = (t[y].ch[1] == x);
if(!isroot(y)) t[z].ch[t[z].ch[1] == y] = x;
t[x].fa = z;
t[y].ch[k] = t[x].ch[k ^ 1];
t[t[x].ch[k ^ 1]].fa=y;
t[x].ch[k ^ 1]=y;
t[y].fa = x;
push_up(y);
push_up(x);
}
void splay(int x)
{
push_all(x);
while(!isroot(x))
{
int y = t[x].fa;
int z = t[y].fa;
if(!isroot(y)) (t[z].ch[1] == y) ^ (t[y].ch[1] == x)? rotate(x) : rotate(y);
rotate(x);
}
}
void access(int x)
{
for(int y = 0; x; y = x, x = t[x].fa) {
splay(x), t[x].ch[1] = y,push_up(x);
}
}
void make_root(int x)
{
access(x); splay(x);
pushr(x);
}
int find_root(int x)
{
access(x); splay(x);
while(t[x].ch[0]) { push_down(x), x = t[x].ch[0]; }
splay(x);
return x;
}
void split(int x,int y)
{
make_root(x);
access(y); splay(y);
}
void link(int x,int y)
{
make_root(x);
if(find_root(y) != x) t[x].fa = y;
}
void cut(int x,int y)
{
make_root(x);
if(find_root(y) == x && t[y].fa == x && !t[y].ch[0])
{
t[x].ch[1] = t[y].fa = 0;
push_up(x);
}
}
}using namespace LCT;
void solve(int i)
{
if(D.find(e[i].u) != D.find(e[i].v))
{
link(e[i].u + m, i); link(e[i].v + m, i);
mg.insert({i}); ms.insert({i}); D.merge(e[i].u, e[i].v);
}else
{
split(e[i].u + m, e[i].v + m);
if(e[t[e[i].v + m].anss].s > e[i].s)
{
int tmp = t[e[i].v + m].anss;
cut(e[tmp].u + m, tmp); cut(e[tmp].v + m, tmp);
mg.erase(mg.find({tmp})); ms.erase(ms.find({tmp}));
link(e[i].u + m, i); link(e[i].v + m, i);
mg.insert({i}); ms.insert({i});
}
}
if(D.sz[D.find(1)] == n) down(res, e[(*mg.begin()).x].g * G + e[(*ms.begin()).x].s * S);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> m >> G >> S;
rep(i, 1, m) cin >> e[i].u >> e[i].v >> e[i].g >> e[i].s;
sort(e + 1, e + 1 + m); D.init(n);
rep(i, 1, m) solve(i);
cout << (res >= INF ? -1 : res) << '\n';
return 0;
}参考文献：
