【洛谷P4172】水管局长
2024-10-06 20:37:53
题目大意：给定 N 个点，M 条边的无向图，支持两种操作：动态删边和查询任意两点之间路径上边权的最大值最小是多少。
题解：
引理：对原图求最小生成树，可以保证任意两点之间的路径上边权的最大值取得最小值。
证明：任取两点 x, y，若 x, y 的路径上最大值最小的边不在最小生成树的路径上，可以将那条边加入最小生成树中，并删去由这条边的加入所带来的环中边权最大的那条边，可以使得最小生成树更小，产生矛盾，证毕。
有了引理之后，问题转化成了维护支持动态删边的最小生成树。发现删边可能会导致最少生成树不断发生变化，每次变化都需要重构生成树，时间复杂度较高。可以采用离线询问，转化成倒序加边的最小生成树的维护，每次加一条边时，只需删除环上最大的那条边即可。支持动态加边和删边，可以采用 lct 进行维护。最后，可以进行点边转化，即：将边缩为一个点，边权为点权，点的点权为 0 即可。
代码如下
#include <bits/stdc++.h>
using namespace std;
struct edge {
int x, y, z;
bool has;
bool operator<(const edge &rhs) {
return this->z < rhs.z;
}
};
struct UFS {
vector<int> f;
UFS(int n) {
f.resize(n + 1);
for (int i = 1; i <= n; i++) {
f[i] = i;
}
}
int find(int x) {
return x == f[x] ? x : f[x] = find(f[x]);
}
bool merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
f[x] = y;
return 1;
}
return 0;
}
};
struct node {
node *l, *r, *p;
int val, maxv, rev, id;
node (int _val = 0, int _id = 0) {
l = r = p = NULL;
val = maxv = _val;
id = _id;
rev = 0;
}
void unsafe_reverse() {
swap(l, r);
rev ^= 1;
}
void pull() {
maxv = val;
if (l != NULL) {
l->p = this;
maxv = max(maxv, l->maxv);
}
if (r != NULL) {
r->p = this;
maxv = max(maxv, r->maxv);
}
}
void push() {
if (rev) {
if (l != NULL) {
l->unsafe_reverse();
}
if (r != NULL) {
r->unsafe_reverse();
}
rev = 0;
}
}
};
bool is_root(node *v) {
if (v == NULL) {
return false;
}
return (v->p == NULL) || (v->p->l != v && v->p->r != v);
}
void rotate(node *v) {
node *u = v->p;
assert(u != NULL);
v->p = u->p;
if (v->p != NULL) { // work with father
if (u == v->p->l) {
v->p->l = v;
}
if (u == v->p->r) {
v->p->r = v;
}
}
if (v == u->l) {
u->l = v->r;
v->r = u;
}
if (v == u->r) {
u->r = v->l;
v->l = u;
}
u->pull();
v->pull();
}
void deal_with_push(node *v) {
static stack<node*> stk;
while (true) {
stk.push(v);
if (is_root(v)) {
break;
}
v = v->p;
}
while (!stk.empty()) {
stk.top()->push();
stk.pop();
}
}
void splay(node *v) {
deal_with_push(v);
while (!is_root(v)) {
node *u = v->p;
if (!is_root(u)) {
if ((u->p->l == u) ^ (u->l == v)) {
rotate(v);
} else {
rotate(u);
}
}
rotate(v);
}
}
void access(node *v) {
node *u = NULL;
while (v != NULL) {
splay(v);
v->r = u;
v->pull();
u = v;
v = v->p;
}
}
void make_root(node *v) {
access(v);
splay(v);
v->unsafe_reverse();
}
node *find_root(node *v) {
access(v);
splay(v);
while (v->l != NULL) {
v->push();
v = v->l;
}
splay(v);
return v;
}
void split(node *u, node *v) {
make_root(u);
access(v);
splay(v);
}
void link(node *u, node *v) {
if (find_root(u) == find_root(v)) {
return;
}
make_root(v);
v->p = u;
}
void cut(node *u, node *v) {
make_root(u);
if (find_root(v) == u && v->p == u && v->l == NULL) {
v->p = u->r = NULL;
u->pull();
}
}
node* find(node *v, int val) {
while (true) {
if (v->val == val) {
break;
}
if (v->l != NULL && v->l->maxv == val) {
v = v->l;
} else {
v = v->r;
}
}
return v;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
vector<node*> t(n + m + 1);
for (int i = 1; i <= n; i++) {
t[i] = new node(0, i);
}
vector<edge> e(m + 1);
map<pair<int, int>, int> id;
for (int i = 1; i <= m; i++) {
int x, y, z;
cin >> x >> y >> z;
if (x > y) {
swap(x, y);
}
e[i] = {x, y, z, 1};
id[{x, y}] = i;
}
vector<pair<int, pair<int, int>>> events(q + 1);
for (int i = 1; i <= q; i++) {
int opt, x, y;
cin >> opt >> x >> y;
if (x > y) {
swap(x, y);
}
events[i] = {opt, {x, y}};
if (opt == 2) {
e[id[{x, y}]].has = 0;
}
}
auto kruskal = [&](vector<edge> ee) {
sort(ee.begin() + 1, ee.end());
UFS ufs(n);
for (int i = 1; i <= m; i++) {
if (ee[i].has == 1) {
int x = ee[i].x, y = ee[i].y, z = ee[i].z;
if (ufs.merge(x, y) == 1) {
int _id = id[{x, y}] + n; // edge_id
t[_id] = new node(z, _id);
link(t[x], t[_id]);
link(t[y], t[_id]);
}
}
}
};
kruskal(e);
vector<int> ans;
for (int i = q; i >= 1; i--) {
int x = events[i].second.first;
int y = events[i].second.second;
int eid = id[{x, y}];
int z = e[eid].z;
if (events[i].first == 1) {
split(t[x], t[y]);
ans.push_back(t[y]->maxv);
} else {
split(t[x], t[y]);
if (t[y]->maxv > z) {
int _id = find(t[y], t[y]->maxv)->id; // edge id
int a = e[_id - n].x, b = e[_id - n].y;
cut(t[a], t[_id]);
cut(t[b], t[_id]);
t[eid + n] = new node(z, eid + n);
link(t[x], t[eid + n]);
link(t[y], t[eid + n]);
}
}
}
reverse(ans.begin(), ans.end());
for (auto v : ans) {
cout << v << endl;
}
return 0;
}
最新文章
- C#检查标准图幅编号
- 在Win7下安装IIS
- inno setup 打包
- struts2的记住账号密码的登录设计
- [AngularJS] Transforming raw JSON data to meaningful output in AngularJS
- 有序线性搜索（Sorted/Ordered Linear Search）
- 转:requirejs打包压缩r.js使用示例
- html 选择器之基础选择器
- 【C++】类中this指针的理解
- Converting Recursive Traversal to Iterator
- JavaScript状态模式及状态机模型
- 185. [USACO Oct08] 挖水井
- Adding ASP.NET MVC5 Identity Authentication to an existing project
- C# 泛型分组和Linq分组的异同
- 使用VS Code写PHP并进行调试
- （转载）jQuery判断checkbox是否选中的3种方法（个人用第二种方法）
- 【刷题】BZOJ 5418 [Noi2018]屠龙勇士
- TCP包服务器接受程序
- 通过SiteMapDataSource动态获取SiteMap文件进行权限设置
- ios基础动画、关键帧动画、动画组、转场动画等