自动搬运

查看原文

来自洛谷，原作者为

	一念之间、、 Have already AFOed.

搬运于2025-08-24 21:38:23，当前版本为作者最后更新于2021-04-18 09:52:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看到两篇题解都是用暴力的方法过的，这个数据真的是比较水，这里提供一个严格复杂度的做法：

考虑两种暴力，

一种是改点时对于每条与它相连边都进行更改（询问快）

一种是在询问的时候考虑暴力枚举边更新答案（修改快）

考虑度数分治，发现度数大于$\sqrt n$的只会最多有$\sqrt n$个考虑将这根号个作为关键点（建立关键点与关键点之间的边）

在非关键点的时候，我们考虑开6个set维护AA,AB,AC,CC,BC,CC的情况(边权排序)

在关键点的时候，分别对每个关键点开三个set维护与它相连的三个颜色

讨论修改，当改一个非关键点，则我们暴力枚举它的所有边，若枚举到的另外一个点是非关键点，则在外边6个set里面改，否则对于另外一个点的关键点内部set进行修改

若当前改一个关键点，我们枚举关键点与关键点之间的边（因为关键点只有$\sqrt n$个，所以复杂度也是$\sqrt n$）对于另外一个关键点进行修改。

考虑询问，对于非关键点之间的边考虑在外部set查询，然后枚举每个关键点，查询以这个关键点和另外颜色边的最小值。

复杂度$O(n\sqrt nlogm)$是不是感觉这个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
*/