题解 P3225 【[HNOI2012]矿场搭建】

· · 题解

/* 首先看到割点就是Tarjan搞 但是怎么搞

首先假设我们把所有的点双都缩点 那么我们一定可以得到一棵树 然后我们就会发现

1.叶子节点(只含有一个割点的点双)必须建 因为叶子节点如果不建 一旦割点被爆就死翘了

2.非叶节点(含有两个或两个以上的割点的点双)不用建 因为即使一个割点被爆了也可以沿着另一个割点走到一个叶节点

3.还有一种情况就是整个联通块都是点双(即不含割点的点双) 这样我们讨论点双的大小

如果只有一个点 那么这个点必须建 数据没有卡这个的点所以我没写(其实是我忘写了 然后还过了)

如果有两个或两个以上的点 那么要建两个 一个被爆了还可以走另一个

方案数就是乘法原理的问题了 注意叶节点那里出口不能建在割点上

所以先Tarjan求割点再dfs一下每个联通块就好了。

*/

#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
int head[505],dfn[505],low[505],vis[505],stack[505];
bool cut[505],in_stack[505];
int n,m,cnt,num,tot,deg,ans1,T,cases,root,top;
ll ans2;
struct node
{
    int from;
    int to;
    int next;
}e[1010];
inline void first()
{
    memset(head,0,sizeof(head));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(cut,0,sizeof(cut));
    memset(vis,0,sizeof(vis));
    top=cnt=tot=n=ans1=T=0; ans2=1;
}
inline void insert(int from,int to)
{
    e[++num].from=from;
    e[num].to=to;
    e[num].next=head[from];
    head[from]=num;
}
inline int read()
{
    int x=0,f=1; char c=getchar();
    while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
void Tarjan(int now,int father)//求割点 
{
    dfn[now]=low[now]=++tot;
    for(int i=head[now];i;i=e[i].next)
        {
            int v=e[i].to;
            if(!dfn[v])
            {
                Tarjan(v,now);
                low[now]=min(low[now],low[v]);
                if(low[v]>=dfn[now])
                {
                    if(now==root) deg++;
                    else cut[now]=true;
                }
            }
            else if(v!=father) low[now]=min(low[now],dfn[v]);//不要跟求环混了 具体原理去网上找 
        }
}
void dfs(int x)//遍历每个连通块 
{
    vis[x]=T;//标记 
    if(cut[x]) return;
    cnt++;//数量 
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].to;
        if(cut[v]&&vis[v]!=T) num++,vis[v]=T;//统计割点数目。 
        //如果是割点且标记不与遍历的的连通块相同就修改标记。 
        if(!vis[v])dfs(v);
    }
}
int main()
{
    m=read();
    while (m)
    {
        first();
        for (int i=1;i<=m;i++)
        {
            int u=read(),v=read();
            n=max(n,max(u,v));//这个地方要处理一下 
            insert(u,v); insert(v,u);
        }
        for (int i=1;i<=n;i++)
        {
            if (!dfn[i]) Tarjan(root=i,0);
            if (deg>=2) cut[root]=1;//根节点的割点 
            deg=0;//不要忘记是多组数据 
        }
        for (int i=1;i<=n;i++)
            if (!vis[i]&&!cut[i])//不是割点 
            {
                T++; cnt=num=0;//T为连通块的标记 
                dfs(i);
                if (!num) ans1+=2,ans2*=cnt*(cnt-1)/2;//建两个 别忘记除以二 因为两个建立的出口没有差异 
                if (num==1) ans1++,ans2*=cnt;//建一个 
            }
        printf("Case %d: %d %lld\n",++cases,ans1,ans2);
        m=read();
    }
    return 0;
}