题解 P5058 【[ZJOI2004]嗅探器】

原来想打tarjan求割点，然后删每一个割点。结果打炸了，愤怒的我敲了一个暴力，然后过了。。。
暴力枚举每一个点，把这个点删除，然后跑spfa，如果a点能到达b点，则不行，否则，这个点就是答案。
PS：无视代码中的tarjan，你会发现把它删了可以跑的更快。。

#include<bits/stdc++.h>
using namespace std;
const int N=1005;
const int M=1000005;
int tot,col,num,ans,n,x[M],y[M],top,head,tail,a,b,sum;
int ne[M],la[M],lnk[M],dfn[N],low[N],co[N],q[N],dis[M];
bool cut[N],vis[M];

int read()
{
    int x=0;char c='a';bool f=false;
    while (c<'0'||c>'9') {c=getchar();if (c=='-') f=1;}
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    if (f) x=x*-1;
    return x;
}

void add(int x,int y)
{
    tot++;ne[tot]=y;la[tot]=lnk[x];lnk[x]=tot;co[tot]=1;
}

void tarjan(int u,int fa)
{
    low[u]=dfn[u]=++num;
    int cnt=0;
    for (int k=lnk[u];k;k=la[k])
    {
        if (!dfn[ne[k]])
        {
            cnt++;
            tarjan(ne[k],fa);
            low[u]=min(low[u],low[ne[k]]);
            if ((u==fa&&cnt>1)||(u!=fa&&dfn[u]<=low[ne[k]])) cut[u]=1;
        }
        else low[u]=min(low[u],dfn[ne[k]]);
    }
    return;
}

void inte()
{
    memset(lnk,0,sizeof(lnk));
    tot=0;
    return;
}

void spfa(int s)
{
    memset(dis,63,sizeof(dis));
    memset(vis,false,sizeof(vis));
    dis[s]=0;vis[s]=1;head=0;tail=1;
    q[1]=s;
    while (head<tail)
    {
        head++;
        int now=q[head];
        for (int k=lnk[now];k;k=la[k])
        {
            if (dis[ne[k]]>=dis[now]+co[k])
            {
                dis[ne[k]]=dis[now]+co[k];
                if (!vis[ne[k]])
                {
                    vis[ne[k]]=1;
                    tail++;
                    q[tail]=ne[k];
                }
            }
        }
        vis[now]=false;
    }
    return;
}

int main()
{
    //freopen("sniffer6.in","r",stdin);
    n=read();
    while (1)
    {
        sum++;
        x[sum]=read();y[sum]=read();
        add(x[sum],y[sum]);add(y[sum],x[sum]);
        if (x[sum]==y[sum]&&x[sum]==0) break;
    }
    a=read(),b=read();
    for (int i=1;i<=n;i++)
    tarjan(i,i);
    for (int i=1;i<=n;i++)
    {
//      if (!cut[i]||i==a||i==b) continue;
        if (i==a||i==b) continue;
        inte();
        for (int j=1;j<=sum;j++)
        if (x[j]==i||y[j]==i) continue;
        else add(x[j],y[j]),add(y[j],x[j]);
        spfa(a);
        if (dis[b]>=200000000) {cout<<i;return 0;}
    }
    cout<<"No solution";
    return 0;
}

题解 P5058 【[ZJOI2004]嗅探器】

原文：https://www.cnblogs.com/xzjds/p/10465039.html