P2302题解
wmy18929355137
·
·
题解
题意
给定无向图 G(V,E) 满足：
-
-
## 思路
首先看见无三元环这个条件很怪，思考 0.1ms 发现等价于 $G$ 中只有 $\geq 4$ 元环。我们假设 $G$ 就是个四元环，可以发现如果 $s \neq t$ 的话，小偷先走一步，然后敌追我跑，敌不动我不动就一定不会被追上。稍微一推广发现 $\geq 4$ 元环警察都追不上。
这时小偷就有一个非常猥琐的策略：
- 如果能走到环里：走到环内然后绕圈
- 如果不能走到环里：到一个最拖时间的地方然后坐着等死
然后思路就出来了。
首先跑个 tarjan 缩点，把在环上的点标记一下，并分别以 $s,t$ 为起点跑个最短路，然后对于每个被标记点看 $s$ 到这个点距离是不是小于 $t$ 到这个点距离，如果是，那么小偷就能走到环内，直接 ``NO``。如果跑了一遍之后没有这样的点，那就选一个最拖时间并且能到达的那个点，输出 $t$ 到它的距离即可。
## code
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,s,t;
vector <int> G[214514];
int cur = 0,ans = 0;
int low[10005],dfn[10005],vis[10005],f[10005];
stack <int> st;
int fl[10005],dis[10005][2];
void bfs01(int u,int x) {
memset(fl,0,sizeof(fl));
queue <pair<int,int> > q;
q.push({u,0});
dis[u][x] = 0;
while (!q.empty()) {
auto now = q.front();
q.pop();
if (fl[now.first]) continue;
fl[now.first] = 1;
for (int v : G[now.first]) {
if (fl[v] != 0) continue;
dis[v][x] = now.second + 1;
q.push({v,now.second + 1});
}
}
}
void tarjan(int u,int fa) {
low[u] = dfn[u] = ++cur;
vis[u] = 1;
st.push(u);
for (int v : G[u]) {
if (v == fa) continue;
if (dfn[v] == 0) {
tarjan(v,u);
low[u] = min(low[u],low[v]);
} else if (vis[v]) {
low[u] = min(low[u],dfn[v]);
}
}
if (low[u] == dfn[u]) {
int cnt = 0;
int x;
do {
x = st.top();
st.pop();
vis[x] = 0;
f[x] = 1;
cnt++;
} while (x != u);
if (cnt == 1) f[x] = 0;
}
}
signed main() {
cin >> n >> m >> s >> t;
// if (s==t) return 1;
for (int i = 1; i <= m; i++) {
int x,y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
if (dfn[i] == 0) tarjan(i,0);
}
bfs01(s,0);
bfs01(t,1);
int res = 0;
for (int i = 1; i <= n; i++) {
if (f[i] && dis[i][0] < dis[i][1]) {
cout << "NO";
exit(0);
}
if (dis[i][1] > dis[i][0]) res = max(res,dis[i][1]);
}
cout << res;
return 0;
}
```