题解 P2500 【[SDOI2012]集合】

· · 题解

话说是洛谷数据有那么水，还是这道省选题本身就是送分题啊......

这道题莫名其妙的弱智。方法很简单，输入边后将边按权值从小到大排序，注意保留每条边的两个端点。开一个数组记录每个点所属的集合。接下来面对每个修改，只需要直接改数组就行了(O(1))。至于查询，只需要从最短边依次检索，找到第一条满足条件的边输出就可以了。如果边全都不合要求，则输出“No Found！”(O(m))。括号里是操作的时间复杂度，最糟糕情况时间复杂度为O(mq)。

代码(话说这么弱智就不用讲太细了吧)：

#include<cstdio>
#include<cstdlib>
#include<cctype>
#include<iostream>
#include<algorithm>
#define For(i,a,b) for((i)=(a);(i)<=(b);++(i))
#define Forward(i,a,b) for((i)=(a);(i)>=(b);--(i))
using namespace std;
const int MAXN=100000+100;
const int MAXM=500000+100;
template<typename T>
inline void read(T &x)//快读
{
    T s=0,f=1;
    char k=getchar();
    while(!isdigit(k)&&k!='-')k=getchar();
    if(k=='-')
    {
        f=-1;
        k=getchar();
    }
    while(isdigit(k))
    {
        s=(s<<3)+(s<<1)+(k^'0');
        k=getchar();
    }
    x=s*f;
}
struct edge
{
    int u,v,w;
    friend bool operator<(edge a,edge b)
    {
        return a.w<b.w;
    }
}p[MAXM];//存边的两端和权值以及重载运算符方便排序
int n,m,belong[MAXN],q;
int cmp,word1,word2;
void get(void)//处理输入
{
    char k=getchar();
    while(!isgraph(k))k=getchar();
    int i;
    if(k=='M')cmp=0;
    else cmp=1;
    For(i,1,3)k=getchar();
    if(k=='A')word1=0;
    else if(k=='B')word1=1;
    else word1=2;
    k=getchar();
    if(k=='A')word2=0;
    else if(k=='B')word2=1;
    else word2=2;
}
int main(void)
{
    int i;
    read(n);
    read(m);
    For(i,1,m)
    {
        read(p[i].u);
        read(p[i].v);
        read(p[i].w);
    }
    sort(p+1,p+m+1);//排序（核心代码（滑稽））
    read(q);
    while(q--)
    {
        get();
        if(cmp==0)
        {
            read(i);
            belong[i]=word2;//修改
        }
        else
        {
            For(i,1,m)if(belong[p[i].u]==word1&&belong[p[i].v]==word2||
                belong[p[i].u]==word2&&belong[p[i].v]==word1)//弱智查询
            {
                printf("%d\n",p[i].w);
                break;
            }
            if(i>m)printf("No Found!\n");
        }
    }
    return 0;
}