题解 P2500 【[SDOI2012]集合】

· · 题解

楼下代码真是高端

这里提供个简明一点的

思路很简单 不要被标签和难度所蒙蔽了

很简单的暴力模拟

先排序然后从小到大找两个端点是否符合询问

集合实际上只要用一个一维数组实现

s[x]=y表示点x属于y集合

y=1时是A，y=2是B，y=3是C

设有一边<u,v>，查顶点属于AB的

注意要查u属于A，v属于B

同时也要看u属于B，v属于A

#include<cstdio>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100001,M=500001,INF=1000000001;
int n,m,q,s[N];
struct edge{int a,b,w;}e[M]; //边
bool cmp(const edge &e1,const edge &e2) //注意定义排序函数
{
    return e1.w<e2.w;
}
int query(int a,int b) //查询
{
    for (int i=1;i<=m;i++)
        if (s[e[i].a]==a&&s[e[i].b]==b||s[e[i].a]==b&&s[e[i].b]==a) //注意是双向查询
            return e[i].w;
    return INF; //如果没找到，注意可能有0或负权，所以不能只是返回0，应返回无穷大
}
inline void ask(int a,int b)
{
    int ans=query(a,b);
    if (ans<INF)printf("%d\n",ans);
    else puts("No Found!");
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++)
        scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].w);
    sort(e+1,e+m+1,cmp); //排序
    for (int i=1;i<=n;i++)s[i]=1; //一开始都属于A
    scanf("%d",&q);
    while (q--)
    {
        string op;int x;
        cin>>op;
        if (op=="MoveA")scanf("%d",&x),s[x]=1;
        if (op=="MoveB")scanf("%d",&x),s[x]=2;
        if (op=="MoveC")scanf("%d",&x),s[x]=3;
        if (op=="AskAA")ask(1,1);
        if (op=="AskAB")ask(1,2);
        if (op=="AskAC")ask(1,3);
        if (op=="AskBB")ask(2,2);
        if (op=="AskBC")ask(2,3);
        if (op=="AskCC")ask(3,3);
    }
    return 0;
}