题解总结起来其实很简单。
把所有的边双联通分量缩成一个点,然后建立好新边, 然后再从起点搜到终点就好了。
代码:
/* code by: zstu wxk time: 2019/02/23 */ #include<bits/stdc++.h> using namespace std; #define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout); #define LL long long #define ULL unsigned LL #define fi first #define se second #define pb push_back #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define lch(x) tr[x].son[0] #define rch(x) tr[x].son[1] #define max3(a,b,c) max(a,max(b,c)) #define min3(a,b,c) min(a,min(b,c)) typedef pair<int,int> pll; const int inf = 0x3f3f3f3f; const int _inf = 0xc0c0c0c0; const LL INF = 0x3f3f3f3f3f3f3f3f; const LL _INF = 0xc0c0c0c0c0c0c0c0; const LL mod = (int)1e9+7; const int N = 3e5 + 100; const int M = N * 2; int n, m; int head[N], to[M], nt[M], val[M], bridge[M]; int tot; void add(int u, int v, int w){ to[tot] = v; nt[tot] = head[u]; val[tot] = w; head[u] = tot++; } int dfn[N], low[N], dtot; void Tarjan(int o, int u){ dfn[u]= low[u] = ++dtot; for(int i = head[u]; ~i; i = nt[i]){ int v = to[i]; if(!dfn[v]){ Tarjan(u, v); low[u] = min(low[u], low[v]); if(low[v] > dfn[u]) bridge[i] = bridge[i^1] = 1; } else if(v != o) low[u] = min(low[u], dfn[v]); } } int c[N], dcc; void dfs(int u){ c[u] = dcc; for(int i = head[u]; i; i = nt[i]){ int v = to[i]; if(c[v] || bridge[i]) continue; dfs(v); } } int ok[N]; vector<pll> vc[N]; void e_dcc(){ for(int i = 1; i <= n; ++i) if(!dfn[i]) Tarjan(0, i); for(int i = 1; i <= n; ++i) if(!c[i]) { ++dcc; dfs(i); } for(int i = 0; i <= tot; i += 2){ int u = to[i^1], v = to[i]; u = c[u], v = c[v]; if(u == v){ ok[u] |= val[i]; } else { vc[u].pb({v,val[i]}); vc[v].pb({u,val[i]}); } } } int flag = 0; int t; void Dfs(int o, int u, int f){ if(u == t){ flag |= f; return ; } for(pll x : vc[u]){ int v = x.fi; if(v == o) continue; Dfs(u, v, f | x.se | ok[v]); } } void Ac(){ int u, v, w; memset(head, -1, sizeof head); for(int i = 1; i <= m; ++i){ scanf("%d%d%d", &u, &v, &w); add(u, v, w); add(v, u, w); } e_dcc(); scanf("%d%d", &u, &v); u = c[u]; t = c[v]; Dfs(0, u, ok[u]); if(flag) puts("YES"); else puts("NO"); } int main(){ while(~scanf("%d%d", &n, &m)){ Ac(); } return 0; }