P5836

Aryper · 2020-03-25 08:58:07 · 个人记录

[USACO19DEC]Milk Visits S

比较巧妙的做法，膜拜想出来这种思路的大佬。

既然判断是否能喝到比较难，那就换一种思考方式，判断是否不能喝到。

很容易想到用并查集直接解决。

并查集处理的思路是这样的

1. 如果两点之间有连边 (不要理解成联通了)。

2. 如果两点的奶牛是相同的。

那么就把这两点放入一个并查集。

在每个朋友提出要求的时候，判断起点和终点是否在一个并查集内，如果在并且奶牛不是朋友要求的奶牛，那么很不幸，这位朋友是不会喝到自己要求的奶牛的，反之则一定会。

代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<vector>
using namespace std;

int u,v,n,m;

int fa[100005];

char ch;

string s,ans;

int find(int x) {
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

void uni(int x,int y) {
    fa[find(x)]=find(y);return;
}

inline int read() {
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') f=-f;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        ret=(ret<<3)+(ret<<1)+ch-'0';
        ch=getchar();
    }
    return ret*f;
}

int main() {

    n=read();m=read();

    cin>>s;

    for(int i=1;i<=n;i++) fa[i]=i;

    for(int i=1;i<n;i++) {
        scanf("%d%d",&u,&v);
        if(s[u-1]==s[v-1]) uni(u,v);
    }

    for(int i=1;i<=m;i++) {
        scanf("%d %d %c",&u,&v,&ch);
        if(ch=='H'&&s[u-1]=='G'&&find(u)==find(v)) {ans=ans+'0';continue;}
        if(ch=='G'&&s[u-1]=='H'&&find(u)==find(v)) {ans=ans+'0';continue;}
        ans=ans+'1';
    }

    cout<<ans;

    return 0;
}