题解 UVA1464 【Traffic Real Time Query System】

2020-07-30 19:24:31


由于我还没调出代码,我就暂时来搪塞一下((没提交)

题目让你求 两条之间的割点个数。

我们显然可以先根据双联通分量缩点。

然后后面的正确性就没数了。

缩点时,我们单独把割点揪出来,单独作为一个分量,其余的缩成一个点。

然后我们考虑统计两条边间的路径上的割点个数。

先树剖,然后 LCA 即可。

统计答案的时候别忘了枚举边的端点,然后取最大值。

时间复杂度 $O(n+q\log_2n)$。

附送错误代码:(调好了记得告诉我错在哪((()

#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
#include<cstring>
namespace Data{int n,m,q,from[2000001],to[2000001];std::vector<int> edge[10001];}
namespace Query{
    std::vector<int> edge[10001],son[10001];int vis[10001],val[10001],belong[10001],dis[10001],top[10001],f[10001],siz[10001],heavy[10001],sum;
    void unique(int u,int fa){vis[u]=1,siz[u]=1;
        for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(v==fa||v==u||vis[v])continue;
            unique(v,u),f[v]=u,son[u].push_back(v),siz[u]+=siz[v],heavy[u]=siz[heavy[u]]>siz[v]?heavy[u]:v;
        }
    }void dfs1(int u){
        for(int i=0;i<son[u].size();i++){int v=son[u][i];dis[v]=dis[u]+val[v],dfs1(v);}
    }void dfs2(int u,int t){top[u]=t;if(heavy[u])dfs2(heavy[u],t);
        for(int i=0;i<son[u].size();i++){int v=son[u][i];if(v!=heavy[u])dfs2(v,v);}
    }int LCA(int x,int y){
        while(top[x]!=top[y])((dis[top[x]]<dis[top[y]])?y:x)=((dis[top[x]]<dis[top[y]])?f[top[y]]:f[top[x]]);
        return (dis[x]<dis[y])?x:y;
    }void init(){
        for(int i=1;i<=Data::n;i++)for(int j=0;j<Data::edge[i].size();j++){int v=Data::edge[i][j];
        edge[belong[i]].push_back(belong[v]);}
        for(int i=1;i<=sum;i++)if(!vis[i])unique(i,0),dis[i]=val[i],dfs1(i),dfs2(i,i);
    }int ask(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
    int get(int x){return belong[Data::from[x]];}int get2(int x){return belong[Data::to[x]];}
    int query(int x,int y){if(get(x)==get(y)&&get2(x)==get2(y))return 0;
        return std::max(std::max(ask(get(x),get(y)),ask(get2(x),get(y))),std::max(ask(get(x),get2(y)),ask(get2(x),get2(y))));
    }void reset(){for(int i=0;i<=Data::n;i++)edge[i].clear(),son[i].clear();
        memset(vis,0,sizeof vis),memset(belong,0,sizeof belong),memset(dis,0,sizeof dis),memset(top,0,sizeof top);
        memset(f,0,sizeof f),memset(siz,0,sizeof siz),memset(heavy,0,sizeof heavy),memset(val,0,sizeof val),sum=0;
    }
}namespace Tarjan{
    int low[100001],dfn[100001],cnt;std::stack<int> sta;
    void tarjan(int u,int f){low[u]=dfn[u]=++cnt,sta.push(u);bool fl=0;
        for(int i=0;i<Data::edge[u].size();i++){int v=Data::edge[u][i];if(v==f)continue;
            if(!dfn[v]){tarjan(v,u),low[u]=std::min(low[u],low[v]);fl=fl|(low[v]>=dfn[u]);}
            else if(!Query::belong[v])low[u]=std::min(low[u],dfn[v]);
        }if(fl){Query::sum++;
            while(sta.top()!=u)Query::belong[sta.top()]=Query::sum,sta.pop();
            Query::belong[u]=++Query::sum,sta.pop(),Query::val[Query::sum]=1;
        }
    }void reset(){memset(low,0,sizeof low),memset(dfn,0,sizeof dfn),cnt=0;while(!sta.empty())sta.pop();}
}using namespace Data;using Tarjan::tarjan;using Query::init;using Query::query;
int main(){while(scanf("%d%d",&n,&m),n+m){
        Tarjan::reset(),Query::reset();
        for(int i=1;i<=n;i++)edge[i].clear();for(int i=1;i<=m;i++){
            scanf("%d%d",from+i,to+i),edge[from[i]].push_back(to[i]),edge[to[i]].push_back(from[i]);
        }for(int i=1;i<=n;i++)if(!Tarjan::dfn[i])tarjan(1,0);init();
        scanf("%d",&q);for(int i=1;i<=q;i++){int u,v;scanf("%d%d",&u,&v),printf("%d\n",query(u,v));}
    }return 0;
}