JZOJ 5305 C先生

题意：

有一个n个点，m条边的图，没有重边、自环，且每一条边最多属于一个环路。

给出q组询问，每次询问u,v两点间的路径有多少种可能。

思路：

先看下方样例说明：

由样例说明可以得知，路径上每经过一个环，路径种数就会乘2，而且最终答案一定是2^n；

因此使用tarjan算法求出图中的环，由于题目限制，求点双联通分量和边双联通分量效果相同。因边双联通分量好写，懒惰的作者采用了它 -~_~-

代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<queue>

 #include<stack>

 #include<vector>

 #define ll long long

 #define MOD 1000000007

 using namespace std;

 vector<int>a[],b[];

 stack<int>s;

 int n,m,q,mm=,dep[],dfn[],low[],fa[],p[][],color[],times,cnt;

 bool vis[],viss[];

 void tarjan(int u){

     int i,j,child=,v;

     s.push(u);vis[u]=;

     dfn[u]=low[u]=times++;

     for(i=;i<a[u].size();i++){

         v=a[u][i];

         if(!vis[v]){

             child++;fa[v]=u;

             tarjan(v);

             low[u]=min(low[u],low[v]);

         }

         else if(v!=fa[u]) low[u]=min(low[u],dfn[v]);

     }

     if(dfn[u]==low[u]){

         cnt++;

         int count=,tmp;

         while(!s.empty()){

             tmp=s.top();

             color[tmp]=cnt+n;

             s.pop();count++;

             if(tmp==u) break;

         }

         if(count==) color[tmp]=tmp;

     }

 }

 void dfs(int u){

     int i,v,t1,t2;t1=color[u];

     viss[t1]=;vis[u]=;

     for(i=;i<a[u].size();i++){

         v=a[u][i];

         t2=color[v];

         if(viss[t2]) goto skip;

         mm++;p[t2][]=t1;dep[t2]=dep[t1]+;

         b[t1].push_back(t2);b[t2].push_back(t1);

         skip:if(vis[v]) continue;

         dfs(v);

     }

     return;

 }

 void init(){

     int i,j;

     for(j=;j<;j++){

         for(i=;i<n+cnt;i++){

             if(!b[i].size()) continue;

             p[i][j]=p[p[i][j-]][j-];

         }

     }

 }

 void shrink(){

     int i,j;

     for(i=;i<=n;i++){

         if(!dfn[i]) tarjan(i);

     }

     memset(vis,,sizeof(vis));memset(viss,,sizeof(viss));

     dep[color[]]=;p[color[]][]=color[];dfs();

     init();

     return ;

 }

 ll calc(int k,int to){

     if(k==to) return (to>n)?:;

     else return calc(p[k][],to)*((k>n)?:);

 }

 ll lca(int l,int r){

     int i,lca,tl=l,tr=r;

     if(dep[l]<dep[r]) swap(l,r);

     int diff=dep[l]-dep[r];

     for(i=;i<;i++){

         if(diff&(<<i)) l=p[l][i];

     }

     if(l==r) lca=l;

     else{

         for(i=;i>=;i--){

             if(p[l][i]!=p[r][i]){

                 l=p[l][i];r=p[r][i];

             }

         }

         lca=p[l][];

     }

     return calc(tl,lca)*calc(tr,lca)/((lca>n)?:);

 }

 int main(){

     int i,t1,t2;

     scanf("%d%d",&n,&m);

     for(i=;i<=n;i++) color[i]=i;

     for(i=;i<=m;i++){

         scanf("%d%d",&t1,&t2);

         a[t1].push_back(t2);a[t2].push_back(t1);

     }

     shrink();

     scanf("%d",&q);

     for(i=;i<=q;i++){

         scanf("%d%d",&t1,&t2);

         printf("%lld\n",lca(color[t1],color[t2])%MOD);

     }

 }

巴特西

JZOJ 5305 C先生

最新文章

热门文章