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

ydc的博客

 
 
 

日志

 
 

bzoj 2730(hnoi2012) mining矿场搭建  

2013-02-09 16:47:03|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

找割点,把割点都干掉,然后就剩下几个不联通的块块。如果某个块块跟多于一个割点接壤就没关系,如果只跟一个割点接壤那么这个块块内部就要取某个点。乘法原理可得就是这些块块的方案数乘一下

如果木有割点,答案就是2与n*(n-1)/2

 

接下来吐槽一下

我是在联赛前学习割点,所以特地找了这题练习

最近在world final上看到了原题,交了一下RE了,一看原题数据范围10^4级别

数组开大再交,WA了

然后发现自己的程序有明显问题!

然后发现自己的求割点代码是错的!

然后发现n<10的随机数据秒出错!

然后无力吐槽HNOI的数据了……

这是我原题的代码,数组是10^4级别

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<map>
#define MAXN 100010
#define MAXM 50010
using namespace std;
typedef long long LL;
int id,color,sum[MAXN],mark[MAXN];
int ans,n,k,dfn[MAXN],low[MAXN],son[MAXN],connect[MAXN];
map<int,int>hash;
int tot,num[MAXN],next[MAXN],start[MAXN];
LL total;
bool use[MAXN],cut[MAXN];
void make(int a,int b){  tot++,num[tot]=b,next[tot]=start[a],start[a]=tot;  }
void Read(int &digit)
{
    digit=0;
    char c;
    for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
    bool type=true;
    if(c=='-')  type=false,c=getchar();
    for(;c>='0'&&c<='9';digit=digit*10+c-'0',c=getchar());
    if(type==false)  digit=-digit;
}
void read()
{
    tot=1,k=0,hash.clear();
    memset(start,0,sizeof(start));
    for(int i=1,a,b;i<=n;i++)
    {
        Read(a),Read(b);
        if(a==b)  continue;
        if(!hash.count(a))  hash[a]=++k;
        if(!hash.count(b))  hash[b]=++k;
        a=hash[a],b=hash[b];
        make(a,b),make(b,a);
    }
}
void Tarjan(int p,int father)
{
    dfn[p]=low[p]=++id,use[p]=true,son[p]=0;
    for(int i=start[p];i;i=next[i])
        if(num[i]!=father)
        {
            int u=num[i];
            if(dfn[u]==0)
            {
                Tarjan(u,p),son[p]++,low[p]=min(low[p],low[u]);
                if(dfn[p]<=low[u]&&father!=-1)  cut[p]=true;
            }
            else if(dfn[u]<dfn[p])  low[p]=min(low[p],low[u]);
        }
    if(son[p]>1&&father==-1)  cut[p]=true;
}
void DFS(int p)
{
    use[p]=true,sum[color]++;
    for(int i=start[p];i;i=next[i])
        if(use[num[i]]==false)
        {
            if(cut[num[i]]==false)  DFS(num[i]);
            else if(mark[num[i]]!=color)  mark[num[i]]=color,connect[color]++;
        }
}
void work()
{
    id=0,ans=0,color=0,total=1;
    memset(dfn,0,sizeof(dfn));
    memset(use,false,sizeof(use));
    memset(cut,false,sizeof(cut));
    memset(sum,0,sizeof(sum));
    memset(connect,0,sizeof(connect));
    for(int i=1;i<=k;i++)
        if(use[i]==false)
            Tarjan(i,-1);
    memset(use,false,sizeof(use));
    memset(mark,0,sizeof(mark));
    for(int i=1;i<=k;i++)
        if(use[i]==false&&cut[i]==false)
        {
            ++color,DFS(i);
            if(connect[color]==1)  ans++,total*=sum[color];
        }
    if(color==1)  ans=2,total=k,total=total*(k-1)/2;
}
int main()
{
    int test=0;
    for(Read(n);n;Read(n))
    {
        read();
        work();
        printf("Case %d: %d %lld\n",++test,ans,total);
    }
    return 0;
}

 


  评论这张
 
阅读(624)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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