[Luogu P3225 [HNOI2012]矿场搭建

题面

P3225 [HNOI2012]矿场搭建


Solution

这题比较妙。

首先,根据常识如果一个点爆了,当且仅当它是割点的时候才会影响整个图的连通性
因此,我们考虑把这道题往点双那方面想。

接下来我们思考这个问题:对于一个点双,我们什么时候需要在它这里面放置逃生通道:
1. 如果与它相连的点双块只有一个:如果爆的是割点,则必须在当前块中的任意点建一个通道;如果爆的是普通点,则当前块则可以与别的块照样联通。
2. 如果与它相连的点双块有两个以上:无论爆的是割点还是普通点,都不影响它里面的其他点到其他块去逃生
综上,我们发现我们只需要在只与1个其他点双块连接的点双块防止逃生通道即可。我在这里暂时称这种块为“叶子点双”。
如下图:我们只需要在紫色的点双块中每一个都放置一个逃生通道即可。

因此,要放置的逃生通道的总数为“叶子点双”的个数,总方案为$\prod (size[x]-1)$ (x为叶子点双)(由乘法原理可得)。

但是,我们要小心一个细节:就是我们在做Tarjan的时候,无论如何都会把1号节点认为是割点。但是,1号节点有可能并不是割点。1号节点有可能属于某一个点双块,而且这个点双块是有可能为叶子节点的,我们做的时候要小心判断一下。

接下来,实现的话就随便写就好。笔者写的时候脑袋有点犯二,就用了圆方树来实现
时间复杂度$O(\sum n)$
就酱,这道题就被我们切掉啦(~ ̄▽ ̄)~


Code

//Luogu P3225 [HNOI2012]矿场搭建
//Apr,8th,2019
//Tarjan求点双+圆方树
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=2*500+20;
vector <int> e[N],e2[N];
int n,m;
int dfn[N],low[N],dfn_to,mstack[N],top,cnt,size[N];
bool vis[N];
void Tarjan(int now,int father)
{
    vis[now]=true;
    low[now]=dfn[now]=++dfn_to;
    mstack[++top]=now;
    for(int i=0;i<int(e[now].size());i++)
        if(vis[e[now][i]]==false)
        {
            Tarjan(e[now][i],now);
            low[now]=min(low[now],low[e[now][i]]);
            if(low[e[now][i]] >= dfn[now])
            {
                e2[now].push_back(n+ ++cnt);
                size[cnt]=1;
                while(mstack[top+1]!=e[now][i])
                    e2[n+cnt].push_back(mstack[top--]),
                    size[cnt]++;
            }
        }
        else if(e[now][i]!=father)
            low[now]=min(low[now],dfn[e[now][i]]);
}
long long ans,ans2;
int dfs(int now)//返回now的子树内的方点个数
{
    int t_cnt=(now>n);
    for(int i=0;i<int(e2[now].size());i++)
        t_cnt+=dfs(e2[now][i]);
    if(now>n and t_cnt==1)
        ans2++,ans*=(size[now-n]-1);
    return t_cnt;
}
bool Check()//判断1所在块是否为叶子块
{
    int x=e2[1][0],t_cnt=0;
    for(int i=0;i<int(e2[x].size());i++)
        if(e2[e2[x][i]].size()!=0)
            t_cnt++;
    return t_cnt==1;
}
int main()
{
    for(int o=1;;o++)
    {
        m=read();
        if(m==0) break;
        for(int i=1;i<=500*2+5;i++)
            e[i].clear(),e2[i].clear();
        dfn_to=cnt=0;
        memset(vis,0,sizeof vis);   

        n=0;
        for(int i=1;i<=m;i++)
        {
            int s=read(),t=read();
            e[s].push_back(t);
            e[t].push_back(s);
            n=max(max(n,s),t);
        }

        Tarjan(1,0);
        ans=1,ans2=0;
        dfs(1);
        if(e2[1].size()==1 and Check()==true)//特殊处理1号节点
            ans*=(size[e2[1][0]-n]-1),
            ans2++;
        if(cnt==1)//特判只有一个连通块的情况
            ans=(n*(n-1))/2,ans2=2;


        printf("Case %d: %lld %lld\n",o,ans2,ans);
    }
    return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注