题目描述
火星猫经过一番努力终于到达了冥王星。他发现冥王星有 (N) 座城市，(M) 条无向边。火星猫准备出发去找冥王兔，他听说有若干泡芙掉落在一些边上，他准备采集一些去送给冥王兔。但是火星猫的火星光环和冥王星相生相克，当火星猫走过一条路之后，这条路就不能再走了。如果冥王兔吃不到泡芙，他们就不能嘿嘿嘿了。所以告诉你火星猫和冥王兔的位置，请问冥王兔能不能吃到泡芙。
输入输出格式
输入格式：
第一行 (N,M) 表示点数和边数。
接下来 (M) 行每行 (X,Y,Z) 表示 $ X $ 到 (Y) 有一条无向边，(Z=1) 表示有泡芙，(Z=0) 表示没有
接下来一行是 (Q)，表示有 (Q)组询问。
每行 (S,T) 表示火星猫和冥王兔的位置。
输出格式：
对于每组询问输出 (YES) 或 (NO)
输入输出样例
输入样例#1：
6 7
1 2 0
2 3 0
3 1 0
3 4 1
4 5 0
5 6 0
6 4 0
1
1 6
输出样例#1：
YES
说明
| (NO.) | (Nleq) | (Mleq) | (Qleq) | 备注 |
|---|---|---|---|---|
| (1-4) | (1000) | (N-1) | (50000) | 保证图是一棵树 |
| (5-8) | (300000) | (N-1) | (300000) | 保证图是一棵树 |
| (9-10) | (20) | (50) | (5) | 无 |
| (11-14) | (1000) | (5000) | (50000) | 无 |
| (15-20) | (300000) | (300000) | (300000) | 无 |
题解
一道我喜欢的(LCA+Tarjan)的题
首先，我们发现若进入了一个环，我们一定可以收集到环上的泡芙（环嘛，可以两边走），若还有出边，则可以出去。
所以，第一步(Tarjan)缩点，并收集每个环中的信息，去建一个新图。
我们会发现新建的图是一个有点权和边权的图，因为无环，所以也是一棵树。
所以可以用(LCA)求出两点之间的最短路径，并记录路径上是否泡芙。
思维量不大，但细节较多，争取自己实现。
code：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cctype>
#define ll long long
#define R register
#define N 300005
using namespace std;
template<typename T>inline void read(T &a){
char c=getchar();T x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
a=f*x;
}
int n,m,q,u[N],v[N],w[N],h[N],tot,fa[N][22],dep[N],dis[N][22];
int top,num,sta[N],dfn[N],low[N],vis[N],cnt,col[N],val[N];
struct node{
int nex,to,dis;
}edge[N<<1];
inline void add(R int u,R int v,R int w){
edge[++tot].nex=h[u];
edge[tot].to=v;
edge[tot].dis=w;
h[u]=tot;
}
inline void tarjan(R int x,R int f){
dfn[x]=low[x]=++num;
sta[++top]=x;vis[x]=1;
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(xx==f)continue;
if(!dfn[xx]){
tarjan(xx,x);
low[x]=min(low[x],low[xx]);
}
else if(vis[xx])low[x]=min(low[x],dfn[xx]);
}
if(dfn[x]==low[x]){
R int now=-1;
cnt++;
while(now!=x){
now=sta[top];
top--;
col[now]=cnt;
vis[now]=0;
}
}
}
inline void dfs(R int x,R int f,R int g){
dep[x]=dep[f]+1;fa[x][0]=f;dis[x][0]=g+val[x];
for(R int i=1;(1<<i)<=dep[x];i++)
fa[x][i]=fa[fa[x][i-1]][i-1],
dis[x][i]=dis[fa[x][i-1]][i-1]+dis[x][i-1];
for(R int i=h[x];i;i=edge[i].nex){
R int xx=edge[i].to;
if(xx==f)continue;
dfs(xx,x,edge[i].dis);
}
}
inline int lca(R int x,R int y){
R int res=0;
if(dep[x]>dep[y])swap(x,y);
for(R int i=20;i>=0;i--)
if(dep[x]<=dep[y]-(1<<i))res+=dis[y][i],y=fa[y][i];
if(x==y)return res+val[x];
for(R int i=20;i>=0;i--)
if(fa[x][i]!=fa[y][i])
res+=dis[x][i],res+=dis[y][i],
x=fa[x][i],y=fa[y][i];
res+=dis[x][0]+dis[y][0]+val[fa[x][0]];
return res;
}
int main(){
read(n);read(m);
for(R int i=1;i<=m;i++){
read(u[i]);read(v[i]);read(w[i]);
add(u[i],v[i],w[i]);add(v[i],u[i],w[i]);
}
for(R int i=1;i<=n;i++)
if(!dfn[i])tarjan(i,0);
memset(h,0,sizeof(h));tot=0;
for(R int i=1;i<=m;i++){
if(col[u[i]]==col[v[i]])
val[col[u[i]]]+=w[i];
if(col[u[i]]!=col[v[i]])
add(col[u[i]],col[v[i]],w[i]),add(col[v[i]],col[u[i]],w[i]);
}
dfs(1,0,0);
read(q);
while(q--){
R int x,y;
read(x);read(y);
x=col[x],y=col[y];
if(lca(x,y))printf("YES
");
else printf("NO
");
}
return 0;
}