P2500 [SDOI2012]集合
看到两篇题解都是用暴力的方法过的，这个数据真的是比较水，这里提供一个严格复杂度的做法：
考虑两种暴力，
一种是改点时对于每条与它相连边都进行更改（询问快）
一种是在询问的时候考虑暴力枚举边更新答案（修改快）
考虑度数分治，发现度数大于
在非关键点的时候，我们考虑开6个set维护AA,AB,AC,CC,BC,CC的情况(边权排序)
在关键点的时候，分别对每个关键点开三个set维护与它相连的三个颜色
讨论修改，当改一个非关键点，则我们暴力枚举它的所有边，若枚举到的另外一个点是非关键点，则在外边6个set里面改，否则对于另外一个点的关键点内部set进行修改
若当前改一个关键点，我们枚举关键点与关键点之间的边（因为关键点只有
考虑询问，对于非关键点之间的边考虑在外部set查询，然后枚举每个关键点，查询以这个关键点和另外颜色边的最小值。
复杂度3s跑不怎么下?
首先这个log跑不满，因为一共只有2m个点加入set，所以算小常数
而且题目保证：无向图上任意两个点之间至多能选出3条不相交的路径。
所以不会出现边全部集中在一堆的情况，也就是卡不掉，实测不开O2跑1秒
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int read()
{
char c;
int w=1;
while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
int ans=c-'0';
while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
return ans*w;
}
int n,m;
const int xx=1e5+5;
struct node
{
int next,to,v;
}e[xx*10];
int cnt;
int h[xx],ds[xx],vis[xx],val[xx*5],uu[xx*5],vv[xx*5];
void add(int x,int y,int z)
{
cnt++;
e[cnt].next=h[x];
h[x]=cnt;
e[cnt].to=y;
e[cnt].v=z;
ds[y]++;
}
node w[xx*5];
int hh[xx];
int cntt;
void add1(int x,int y,int z)
{
cntt++;
w[cntt].next=hh[x];
hh[x]=cntt;
w[cntt].to=y;
w[cntt].v=z;
}
int id[xx*5],bel[xx];
bool cmp(int x,int y){return ds[x]>ds[y];}
struct nod
{
int x;
nod(){}
nod(int a):x(a){}
bool operator<(const nod&w)const{return x<w.x;}//只加入边权
};
int to[4][4],ts[xx];
struct no
{
multiset<nod>s[4];
int get(int id)
{
if(!s[id].size())return 2147483647;
return (*s[id].begin()).x;
}
void add(int x,int op,int id)
{
if(op==-1)s[id].erase(s[id].find(nod(x)));
else s[id].insert(nod(x));
}
}t[351];
multiset<nod>s[7];
int get(int id)
{
if(!s[id].size())return 2147483647;
return (*s[id].begin()).x;
}
void adds(int x,int op,int id)
{
if(op==-1)s[id].erase(s[id].find(nod(x)));
else s[id].insert(nod(x));
}
//用set存，和个数有关
int main(){
to[1][1]=1;
to[1][2]=to[2][1]=2;
to[1][3]=to[3][1]=3;
to[2][2]=4;
to[2][3]=to[3][2]=5;
to[3][3]=6;
n=read();
m=read();
for(int i=1;i<=n;i++)bel[i]=1;
for(int i=1;i<=m;i++)
{
id[i]=i;
int a,b;
a=uu[i]=read();
b=vv[i]=read();
val[i]=read();
add(a,b,val[i]);
add(b,a,val[i]);
}
sort(id+1,id+m+1,cmp);
for(int i=1;i<=min(350,n);i++)vis[id[i]]=1,ts[id[i]]=i;
for(int i=1;i<=m;i++)
{
int a=uu[i],b=vv[i];
if(vis[a]&&vis[b])add1(a,b,val[i]),add1(b,a,val[i]),t[ts[a]].add(val[i],1,1),t[ts[b]].add(val[i],1,1);
else if(!vis[a]&&!vis[b])adds(val[i],1,1);
else
{
if(vis[a])swap(a,b);//visa=0visb=1
t[ts[b]].add(val[i],1,1);
}
}
int q=read();
for(int aa=1;aa<=q;aa++)
{
char s[10];
scanf("%s",s);
if(s[0]=='A')
{
int a=s[3]-'A'+1,b=s[4]-'A'+1;
int minn=get(to[a][b]);
for(int i=1;i<=min(350,n);i++)
{
if(bel[id[i]]!=a&&bel[id[i]]!=b)continue;
minn=min(minn,t[i].get((bel[id[i]]==a)?b:a));
}
if(minn==2147483647)puts("No Found!");
else cout<<minn<<"\n";
}
else //s[4]
{
int x=read();
int a=s[4]-'A'+1;
if(bel[x]==a)continue;
if(vis[x])
{
for(int i=hh[x];i;i=w[i].next)
{
t[ts[w[i].to]].add(w[i].v,-1,bel[x]);
t[ts[w[i].to]].add(w[i].v,1,a);
}
}
else
{
for(int i=h[x];i;i=e[i].next)
{
if(vis[e[i].to])
{
t[ts[e[i].to]].add(e[i].v,-1,bel[x]);
t[ts[e[i].to]].add(e[i].v,1,a);
}
else
{
adds(e[i].v,-1,to[bel[x]][bel[e[i].to]]);
adds(e[i].v,1,to[a][bel[e[i].to]]);
}
}
}
bel[x]=a;
}
}
return 0;
}
/*
A 1 AA 1 BB 4
B 2 AB 2 BC 5
C 3 AC 3 CC 6
*/