P2500 [SDOI2012] 集合 题解
Meika_Mikoto
·
·
题解
Introduction
# Solution
$n$ 方过百万，暴力辗标算。
输入边的信息后将边按边权从小到大排序并开一个数组或 $set$ 记录每个点所属的集合。
接下来修改时，直接改数组就行了。
查询时只需要从边权最短的边依次检查，找到第一条满足条件的边输出。
最劣时间复杂度：$\Theta(mq)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0;
short f=1;
char c=getchar();
while(c>57||c<48){
if(c==45) f=-1;
c=getchar();
}
while(c<58&&c>47){
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
inline void write(int x){
if(x<0ll) putchar(45),x=~x+1;
if(x>9ll) write(x/10);
putchar(x%10|48);
}
struct edge{
int u,v,w;
friend bool operator<(edge x,edge y){
return x.w<y.w;
}
}e[5000001];
int n,m,ans,q,dacty[1000001];
string s;
signed main(){
n=read();
m=read();
for(int i=1;i<=m;i++){
e[i].u=read();
e[i].v=read();
e[i].w=read();
}
sort(e+1,e+m+1);
for(int i=1;i<=n;i++) dacty[i]=1;
q=read();
while(q--){
cin>>s;
if(s[0]=='M'){
int x=read();
if(s[4]=='A'){
dacty[x]=1;
}
else if(s[4]=='B'){
dacty[x]=2;
}
else if(s[4]=='C'){
dacty[x]=3;
}
}
else{
ans=INT_MAX;
if(s[3]=='A'&&s[4]=='A'){
for(int i=1;i<=m;i++){
if(dacty[e[i].u]==1&&dacty[e[i].v]==1){
ans=e[i].w;
break;
}
}
}
else if(s[3]=='A'&&s[4]=='B'){
for(int i=1;i<=m;i++){
if((dacty[e[i].u]==1&&dacty[e[i].v]==2)||(dacty[e[i].u]==2&&dacty[e[i].v]==1)){
ans=e[i].w;
break;
}
}
}
else if(s[3]=='A'&&s[4]=='C'){
for(int i=1;i<=m;i++){
if((dacty[e[i].u]==1&&dacty[e[i].v]==3)||(dacty[e[i].u]==3&&dacty[e[i].v]==1)){
ans=e[i].w;
break;
}
}
}
else if(s[3]=='B'&&s[4]=='B'){
for(int i=1;i<=m;i++){
if(dacty[e[i].u]==2&&dacty[e[i].v]==2){
ans=e[i].w;
break;
}
}
}
else if(s[3]=='B'&&s[4]=='C'){
for(int i=1;i<=m;i++){
if((dacty[e[i].u]==2&&dacty[e[i].v]==3)||(dacty[e[i].u]==3&&dacty[e[i].v]==2)){
ans=e[i].w;
break;
}
}
}
else if(s[3]=='C'&&s[4]=='C'){
for(int i=1;i<=m;i++){
if(dacty[e[i].u]==3&&dacty[e[i].v]==3){
ans=e[i].w;
break;
}
}
}
if(ans==INT_MAX){
printf("No Found!\n");
}
else{
write(ans);
printf("\n");
}
}
}
return 0;
}
```
## [record](https://www.luogu.com.cn/record/149935752)
跑的最慢的也就 $131ms$。