SDOI2012 集合
题意
小H在学习“集合与图论”的时候遇到了一个问题，他思考了很久依然无法很好完成这个问题。于是他只好来求助你了，给出n个点m条边的带权无向图（即每条无向边上都有一个权值），有3个集合A、B、C。一开始无向图中所有点都属于A集合，有如下9种操作：
MoveA x：表示将第x个点从所在集合中删除，并加入至A集合。
MoveB x：表示将第x个点从所在集合中删除，并加入至B集合。
MoveC x：表示将第x个点从所在集合中删除，并加入至C集合。
AskAA：询问两个端点都属于A集合的所有边中最小的权值是多少。
AskAB：询问两个端点分别属于A集合和B集合的所有边中最小的权值是多少。
AskAC：询问两个端点分别属于A集合和C集合的所有边中最小的权值是多少。
AskBB：询问两个端点都属于B集合的所有边中最小的权值是多少。
AskBC：询问两个端点分别属于B集合和C集合的所有边中最小的权值是多少。
AskCC：询问两个端点都属于C集合的所有边中最小的权值是多少。
你能帮助他解决这个问题吗？
数据范围:
对于其中20%的数据，满足n<=50, m<=2500, q<=2500。
对于另外30%的数据，满足n<=100, m<=10000, q<=20000。
对于另外50%的数据，满足n<=100000,m<=500000,q<=100000。且无向图上任意两个点之间至多能选出3条不相交的路径。
题解
一道数据太水的好题啊……
首先我们考虑如何在树上维护这个东西，发现我们只需要对于每一个点，将其孩子节点边权放入该点对应颜色的集合中，然后再维护一个全局的(set)来维护每一种询问的答案即可。修改的时候只需要更新孩子节点和父亲节点就可以了。然后我们考虑这个题的特殊性质，任意两点之间至多能够选出3条不相交的路径。这个性质看起来并没有什么卵用，但是我们考虑将这条路径看成网络流的一条增广路，然后这个题的性质就相当于任意两个点之间最大流为3。考虑我们进行最小生成树的过程，每做一次最小生成树，两点之间的最大流最少会减少1，那么我们至多可以将这个图分成三棵生成森林，这样我们将其分成三棵森林之后，就可以分开来维护，然后一起取个max就行了。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 500;
const int M = 5e5 + 500;
const int inf = 0x3f3f3f3f;
typedef pair<int, int> P;
#define fi first
#define se second
#define mk make_pair
int n, m, q;
struct edge {
int u, v, w;
bool operator < (const edge &rhs) const {
return w < rhs.w;
}
}E[M];
int Turn(int a, int b) {
if(a > b) swap(a, b);
if(a == 0 && b == 0) return 0;
if(a == 0 && b == 1) return 1;
if(a == 0 && b == 2) return 2;
if(a == 1 && b == 1) return 3;
if(a == 1 && b == 2) return 4;
if(a == 2 && b == 2) return 5;
}
struct Edge {
int to, w, idx;
};
vector<Edge> F[N];
namespace Solver1 {
multiset<edge> S[6];
vector<P> G[N];
int col[N];
void Delete(int x) {
for(int j = 0; j < (int)G[x].size(); j++) {
int to = G[x][j].fi, id = G[x][j].se;
int pos = Turn(col[x], col[to]);
S[pos].erase(E[id]);
}
}
void Insert(int x) {
for(int j = 0; j < (int)G[x].size(); j++) {
int to = G[x][j].fi, id = G[x][j].se;
int pos = Turn(col[x], col[to]);
S[pos].insert(E[id]);
}
}
void main() {
for(int i = 1; i <= m; i++) {
S[0].insert(E[i]);
int u = E[i].u, v = E[i].v;
G[u].push_back(mk(v, i));
G[v].push_back(mk(u, i));
}
for(int i = 1; i <= q; i++) {
char s[10];
scanf("%s",s);
if(s[0] == 'A') {
int a = s[3] - 'A', b = s[4] - 'A';
int pos = Turn(a, b);
if(!S[pos].size()) puts("No Found!");
else printf("%d
", (*S[pos].begin()).w);
}
else {
int x, pos = s[4] - 'A';
scanf("%d", &x);
Delete(x);
col[x] = pos;
Insert(x);
}
}
}
}
namespace Solver2 {
int vis[M];
struct Tree {
int fa[N], ret[N][6], v[N], c[N];
vector<int> G[N], rt;
multiset<int> col[N][3], C[6];
void Dfs(int o, int f) {
// cerr << "o:" << o << " f:" << f << endl;
fa[o] = f;
memset(ret[o], 0x3f, sizeof ret[o]);
for(int i = 0; i < (int)F[o].size(); i++) {
Edge& e = F[o][i];
if(e.to == f || vis[e.idx] || fa[e.to]) continue;
vis[e.idx] = 1; v[e.to] = e.w;
G[o].push_back(e.to); col[o][0].insert(e.w);
ret[o][0] = min(ret[o][0], e.w);
Dfs(e.to, o);
}
if(ret[o][0] < inf) C[0].insert(ret[o][0]);
}
void Build() {
for(int i = 1; i <= n; i++) {
if(!fa[i]) {
Dfs(i, -1), rt.push_back(i);
}
}
}
void Update(int o) {
for(int i = 0; i < 6; i++) {
if(ret[o][i] == inf) continue;
C[i].erase(C[i].find(ret[o][i])); ret[o][i] = inf;
}
for(int i = 0; i < 3; i++) {
int pos = Turn(c[o], i);
if(!col[o][i].size()) ret[o][pos] = inf;
else ret[o][pos] = *col[o][i].begin(), C[pos].insert(ret[o][pos]);
}
}
void Modify(int o, int co) {
if(c[o] == co) return ;
if(~fa[o]) {
col[fa[o]][c[o]].erase(col[fa[o]][c[o]].find(v[o]));
c[o] = co;
col[fa[o]][c[o]].insert(v[o]);
Update(fa[o]); Update(o);
}
else c[o] = co, Update(o);
}
int Query(int co) {
if(!C[co].size()) return -1;
return *C[co].begin();
}
}T[3];
void main() {
for(int i = 1; i <= m; i++) {
int u = E[i].u, v = E[i].v, w = E[i].w;
F[u].push_back((Edge) {v, w, i});
F[v].push_back((Edge) {u, w, i});
}
for(int i = 0; i < 3; i++) T[i].Build();
for(int i = 1; i <= q; i++) {
char s[10];
scanf("%s",s);
if(s[0] == 'A') {
int a = s[3] - 'A', b = s[4] - 'A';
int pos = Turn(a, b);
int ans = inf;
for(int j = 0; j < 3; j++) {
int ret = T[j].Query(pos);
if(~ret) ans = min(ans, ret);
}
if(ans == inf) puts("No Found!");
else printf("%d
", ans);
}
else {
int x, pos = s[4] - 'A';
scanf("%d", &x);
for(int j = 0; j < 3; j++) {
T[j].Modify(x, pos);
}
}
}
}
}
namespace Solver3 {
int col[N];
void main() {
sort(E + 1, E + 1 + m);
for(int i = 1; i <= q; i++) {
char s[10];
scanf("%s",s);
if(s[0] == 'A') {
int a = s[3] - 'A', b = s[4] - 'A';
int pos = Turn(a, b);
int f = 0;
for(int j = 1; j <= m; j++) {
int u = E[j].u, v = E[j].v;
if(Turn(col[u], col[v]) == pos) {
printf("%d
", E[j].w);
f = 1;
break;
}
}
if(!f) puts("No Found!");
}
else {
int x, pos = s[4] - 'A';
scanf("%d", &x);
col[x] = pos;
}
}
}
}
int main() {
scanf("%d%d",&n, &m);
for(int i = 1; i <= m; i++) scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
scanf("%d", &q);
if(n <= 100 && m <= 10000 && q <= 20000) Solver3::main();
else Solver2::main();
return 0;
}