P5058 [ZJOI2004] 嗅探器

_XHY20180718_ · 2023-11-17 12:05:06 · 个人记录

这道题有很多做法，可是题解区无一例外都是清一色的 tarjan，这里提供一种哈希做法。

简要题意：

给你一张图，求出 s 到 t 一定会经过的点中编号最小的那个。

思路：

什么圆方树，LCT 的做法我都不会呀，这里讲一个哈希的做法。

先将图 dfs 遍历一遍，求出从 s 到 t 的简单路径所有可能会经过的边与点，建出一张有向无环图，然后给 f_s 随便赋一个初值，对此 DAG 遍历一遍，将每个点的 f 其平均分给他的出边，出边加上这些分给他们的权值。

遍历完之后，我们判断哪些点的 f 和 f_s 是否一样，一样就输出这个点的编号，然后这题就做完了。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=5e5+5;
const long double L=1ll*32*27*25*7*11*13*17*19;
const long double eps=1e-10;
int n,m,s,t,rd[N];
int dfn[N],low[N],Time;
int head[N],ei,st[N],r;
bool is[N],cut[N],vis[N];
long double f[N];
vector<int>E[N];
struct edge{
    int v,nxt;
}egs[M<<1];
inline void add(int u,int v)
{egs[++ei]={v,head[u]};head[u]=ei;}
bool dfs(int fa,int u){
    bool flag=0;st[++r]=u;vis[u]=1;
    if(u==t){if(r>1)
        E[st[r-1]].push_back(st[r]),++rd[st[r]];
        is[st[r--]]=1;return 1;
    }
    for(int i=head[u];i;i=egs[i].nxt){
        const int v=egs[i].v;
        if(v==fa)continue;
        if(!vis[v])flag|=dfs(u,v);
        else if(is[v])flag|=1,
            E[st[r]].push_back(v),++rd[v];
    }
    if(flag){if(r>1)
        E[st[r-1]].push_back(st[r]),++rd[st[r]];
        is[st[r--]]=1;
    }else --r;
    return flag;
}
void bfs(){queue<int>qu;qu.push(s);
    while(!qu.empty()){
        const int u=qu.front();qu.pop();
        if(!E[u].size())continue;
        long double w=f[u]/E[u].size();
        for(int v:E[u])
        {f[v]+=w;if(!--rd[v])qu.push(v);}
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;int u,v;
    while(cin>>u>>v){
        if(!u&&!v)break;
        if(u^v)add(u,v),add(v,u);
    }ei=0;cin>>s>>t;f[s]=L;
    dfs(0,s);bfs();
    for(u=1; u<=n; ++u)
        if((u^s)&&(u^t)&&fabs(f[u]-f[s])<eps)
            cout<<u<<'\n',exit(0);
    cout<<"No solution\n";
    return 0;
}