比赛场次 481
比赛名称 20160309
比赛状态 已结束比赛成绩
开始时间 2020-08-01 18:00:00
结束时间 2020-08-01 23:00:00
开放分组 全部用户
注释介绍
题目名称 集合
输入输出 seta.in/out
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar瑆の時間~無盡輪迴·林蔭 AAAAAAAAAA 2.174 s 15.81 MiB 100

集合

★☆   输入文件:seta.in   输出文件:seta.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目描述】


小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集合的所有边中最小的权值是多少。

  你能帮助他解决这个问题吗?


【输入格式】


输入的第1行有两个正整数,分别表示n和m。

  在第2行至第m+1行中,每行有三个正整数,分别为u、v、w。表示这条无向边的两个端点分别为u和v(u != v),且这个边的权值为w(w<=10^9)。

  第m+2行有一个正整数q,表示有q个询问。

  在第m+3行至第m+q+2行中,每行的输入方式为题目描述里9种操作中的一种。


【输出格式】

对于所有的Ask操作输出最小的权值,如果不存在则输出“No Found!”。

【样例输入】

4 3
1 2 1 
2 3 2
3 1 3
5
AskAA
AskAB
MoveB 2
AskAA
AskAB

【样例输出】

1
No Found!
3
1

【提示】


数据范围

对于其中20%的数据,满足n<=50, m<=2500, q<=2500。

对于另外30%的数据,满足n<=100, m<=10000, q<=20000。

对于另外50%的数据,满足n<=100000,m<=500000,q<=100000。且无向图上任意两个点之间至多能选出3条不相交的路径。


【来源】

在此键入。