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

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2389]XY的赛车场  

2015-01-05 20:49:56|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2389: XY的赛车场

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 73  Solved: 47
[Submit][Status]

Description

      神牛XY是一中信息组最牛逼,也是最富有的孩子,而他又是一个赛车迷。XY神牛要成年了,所以他的父亲XZG准备给他建一座赛车场。XZG要建这座赛车场上有N个连接点,建M截直道,连接这N个连接点(不存在从I到I的直道)。而建这M截直道是有顺序的,按从1到M建。
对于建设过程中的赛车场,XZG希望知道这时XY是否可以使用赛车场了,使用的方法有几 种。而赛车场可以使用的标准如下:1.赛车跑道必须由已建的直道组成,即选出组成赛车跑道的直道是已建直道的子集。2.赛车跑道必须是封闭的、,即必须从 任意一个点出发可以回到这个点。3.每个连接点可以多次经过,但是每条直道只能经过一次。
XZG想知道对于修好第1至第M条直道后可行的组成赛车场的方案有多少种。

Input

      输入第一行是两个数N和M。
       接下来M行,每行两个数A,B,表示第I条直道连接A到B。

Output

      M行,每行一个数SI表示表示连接了第I条直道后的方案数。由于答案较大,所以答案MOD 10^9+9。

Sample Input

3 4
1 3
2 3
1 2
1 2

Sample Output

0
0
1
3

HINT

Data Limit
对于10%的数据,1≤N≤10,1≤M≤10;
对于40%的数据,1≤N≤1000,1≤M≤50000;
对于100%的数据,1≤N≤500000,1≤M≤1000000;

Solution

题意就是求一张图内的回路条数,要求不能重复走一条路,可以不把图联通

我们知道,一条路只有走与不走的两种状态,当加入这条边时,如果这条边所连接的两个端点已经联通,ans=ans*2+1,因为所有的方案可以把这条边包括进来,构造出来一种新的方案。用并查集维护就可以了。

这就是代码只有300B的原因

Code

/**************************************************************
    Problem: 2389
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2184 ms
    Memory:2760 kb
****************************************************************/
 
#include<cstdio>
int n,m,fa[500010],x,y,p=1000000009,z=1,aa;int F(){return scanf("%d",&aa),aa;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
    for(n=F(),m=F();n;n--)fa[n]=n;
    for(;m--;printf("%d\n",z-1))x=gf(F()),y=gf(F()),x!=y?fa[x]=y:z=(z<<1)%p;
}
  评论这张
 
阅读(57)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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