P2500 [SDOI2012]集合

    • 49通过
    • 84提交
  • 题目提供者 kkksc03 站长团
  • 评测方式 云端评测
  • 标签 数论,数学 最大公约数,gcd 高斯消元 各省省选 2012 山东
  • 难度 省选/NOI-
  • 时空限制 3000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小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!”。

    输入输出样例

    输入样例#1: 复制
    4 3
    1 2 1 
    2 3 2
    3 1 3
    5
    AskAA
    AskAB
    MoveB 2
    AskAA
    AskAB
    输出样例#1: 复制
    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条不相交的路径。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。