注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

OI之路,漫漫人生

只为梦想,没有理由

 
 
 

日志

 
 

tarjan强通(bzoj2438)  

2014-07-03 21:55:59|  分类: 算法杂类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
此题强连通分量的选错概率为1/n,缩点后统计入度为0的点,特殊情况只剩下一个点时,因理智上可以判断,故需特判。如:
3 1 3 2
1 2 或者1 2 
3 2
都只需2/3概率即可。然后一个点是最后一个点:size=1,入度=0,要么没有边,要么所有与它相连的边的size都大于1;

tarjan模板,算法见推荐阅读
#include<cstdio>
#define mm 300100
#define nn 100100
using namespace std;
struct node{int end,next;}g[mm*2];
int f1[nn],v[nn],c[nn],size[nn],dfsn[nn],low[nn],d[nn],stack[nn],f2[nn];
int tot,dex,u,n,m,i,j,x,y,col,ans;
 
int min(int a,int b){return (a>b)?b:a;}
 
void add(int a,int b,int flag)
 {g[++tot].end=b;
  if (flag==1){g[tot].next=f1[a];f1[a]=tot;}
  else {g[tot].next=f2[a];f2[a]=tot;}
 }
void tarjan(int w)
 {dfsn[w]=low[w]=++dex;
  v[stack[++stack[0]]=w]=1;
  for (int i=f1[w],u;i;i=g[i].next)
       if (!dfsn[u=g[i].end])
             {tarjan(u);
              low[w]=min(low[w],low[u]);
             }else if (v[u])
             low[w]=min(low[w],dfsn[u]);
 if (low[w]==dfsn[w])
          {col++;
       do{v[stack[stack[0]]]=0;
          c[stack[stack[0]]]=col;
         }while (stack[stack[0]--]!=w);
          }
 }
int main()
{
 scanf("%d%d",&n,&m);
 for (i=1;i<=m;i++)
    scanf("%d%d",&x,&y),add(x,y,1);
  
 dex=0;
 for (i=1;i<=n;i++)
  if (!dfsn[i])tarjan(i);
  
  
 for (i=1;i<=n;i++){
     size[c[i]]++;
    for (j=f1[i];j;j=g[j].next)
        if (c[u=g[j].end]!=c[i])add(c[i],c[u],2);              
                   }
  
 for (i=1;i<=n;i++)
  for (j=f2[i];j;j=g[j].next)
    if (v[u=g[j].end]!=i){v[u]=i;d[u]++;}
  
 bool f=true;ans=0;
 for (i=1;i<=col;i++)if (!d[i])
                if (size[i]==1){
                bool ff=true;
                for (j=f2[i];j&&ff;j=g[j].next)
                    if (d[g[j].end]==1)ff=false;
                if (ff&&f)f=false;
                else ans++;   
                               }else ans++; 
 printf("%.6lf\n",1.0*(n-ans)/n);
 return 0;
}
  评论这张
 
阅读(43216)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018