NC15095. 合成反应
描述
输入描述
第一行输入四个整数 K,N,M,Q（K,N,M,Q<=1e5）
K表示一共K总物质
接下来N行 每行三个数字a b c（任意两个数可能相等）
表示a和b反应可以生成c 反应是可逆的
即可以通过c可以分解出a和b
接下来一行行然后输入m个数，表示m种原料（每一种原料都可以认为有无限多）
接下来Q个行Q个询问
对于每个询问
输出一个数字 x 判断是否可以通过一些反应得到第 x
输出描述
可以得到Yes否则No
示例1
输入:
10 3 4 10 1 2 3 4 5 6 2 5 7 3 4 5 8 1 2 3 4 5 6 7 8 9 10
输出:
Yes Yes Yes Yes Yes Yes Yes Yes No No
说明:
一共10总物质有第3，4，5，8 四种原料C++11(clang++ 3.9) 解法, 执行用时: 317ms, 内存消耗: 4548K, 提交时间: 2020-02-29 18:26:54
#include<bits/stdc++.h>
using namespace std;
#define maxn 100001
int a[maxn],b[maxn],c[maxn],f[maxn];
int main()
{
int k,n,m,q,i,j,d,x;
cin>>k>>n>>m>>q;
for(i=0;i<n;i++)
cin>>a[i]>>b[i]>>c[i];
for(i=0;i<m;i++)
{
cin>>d;
f[d]=1;
}
d=sqrt(n);
while(d--)
for(j=0;j<n;j++)
{
if(f[a[j]]&&f[b[j]])
f[c[j]]=1;
else if(f[c[j]])
f[a[j]]=1,f[b[j]]=1;
}
while(q--)
{
cin>>x;
if(f[x])
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}