题解 P5058 【[ZJOI2004]嗅探器】

首先非常明显的是，只能把服务器建在**割点**上，因为只有这样，才能捕获到全部的数据。 考虑如何求x,y两点之间的必经的割点。 很明显需要满足4个条件 考虑我们有一个u点，它连了一个v点，那么u点需要满足4个条件。 1. u不是起点终点。因为题目要求在中间服务器上建嗅探器。 2. u是割点。~~废话~~ 3. 终点(y)的dfn应该**大于等于**v点的dfn，因为要确保终点在v点或之后被访问到，即u点为必经的点。 4. 终点(y)的low应该**大于等于**u点的dfn，因为要确保终点必须要经过u点。 剩下的没什么了，板子 注意我们从x点开始tarjan，就不用看x点是不是割点了。 ``` #include<cstdio> const int N=1e5+50; const int M=5e5+50; int to[M<<1],las[M<<1],fir[M<<1],cnt; inline void add_edge(int u,int v){ to[++cnt]=v;las[cnt]=fir[u];fir[u]=cnt; to[++cnt]=u;las[cnt]=fir[v];fir[v]=cnt; } int dfn[N],low[N],tot; int gd[N]; int n,m,x,y; int opt,ans=N; inline int max(int u,int v){return u>v?u:v;} inline int min(int u,int v){return u<v?u:v;} void tj(int u){ dfn[u]=low[u]=++tot; for(int i=fir[u];i;i=las[i]){ if(!dfn[to[i]]){ tj(to[i]); low[u]=min(low[u],low[to[i]]); if(u!=x&&u!=y)//不是起点终点 if(dfn[u]<=low[to[i]]&&dfn[to[i]]<=dfn[y]&&low[y]>=dfn[x])//满足条件 ans=min(ans,u);//更新答案 } low[u]=min(low[u],dfn[to[i]]); } } int main(){ scanf("%d",&n); while(scanf("%d%d",&x,&y),x)add_edge(x,y); //建边 scanf("%d%d",&x,&y);//读入起点和终点 tj(x);//从x点tarjan if(ans!=N)printf("%d\n",ans); else puts("No solution"); } ``` ~~数据范围可以开大一些~~