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

这道题目真是挺难的：主要的算法就是tarjan,以及点双连通以及最后对答案的处理用到的组合数学。

题目传送门：P3225 [HNOI2012]矿场搭建

题目大概意思：就是有很多个点，在某个时候一个点将会塌陷，你要建造一些点，使他们在那个点塌陷时成功逃脱！

此时我们要分类讨论三种情况：

情况一：在一个强连通中没有一个割点（见下图）

那么此时至少要建立两个点，使得在点坍塌时能顺利逃脱，那么此时要建立的点的个数就是2*sum1(sum1就是强连通的个数)，而方案数则是C(n,2)->(n*(n-1)/2)

情况二：在一个强连通中有一个割点（见下图）

绿色的点即为割点，此时在一个强连通分量中只要建立1个即可，那么总共需要建立sum1个（sum1意义同上）；

情况三：在一个强连通中有两个割点（见下图）

绿色的点即为割点，此时就不需要建立任何东西，因为可以逃脱，互相连通的，此时就无需操作

以上就是本题的关键之一，下一步就是点双，点双就很简单啦，模板一发就好啦！那我就贴代码啦吧，有点长哦！

// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int maxn=5e2+5;
struct Node 
{
    int u,v;
};
struct node
{
    int nex,to;
}ee[maxn];
vector<int> ma[maxn]; //用来存储该点双联通分量的所有顶点 
stack<Node> st;//STL栈
int cut[maxn],dfn[maxn];
int col[maxn],siz[maxn];
int head[maxn],cnt,now,sum,rt,top;
int res1,res2,Case,wyy[maxn],iscut,n;
inline void add_edge(int u,int v) 
{
    ee[++cnt].nex=head[u];
    head[u]=cnt;
    ee[cnt].to=v;
}//前向星连边
inline int read() 
{
    int z=0,f=1;char k;
    while(k<'0'||k>'9'){if(k=='-')f=-1;k=getchar();}
    while(k>='0'&&k<='9'){z=(z<<3)+(z<<1)+k-'0';k=getchar();}
    return z*f;
}
inline int tarjan(int u,int fa) //点双模板，大致介绍一下
// u是当前点，fa是父亲点; 
{
    int lowu=dfn[u]=++now;
    int son=0;
    for ( re int i=head[u];i;i=ee[i].nex )
    {
        int v=ee[i].to;
        Node e=(Node){u,v};
        if(!dfn[v])
        {
            son++;
            st.push(e);
            int lowv=tarjan(v,u);
            lowu=min(lowu,lowv);
            if(lowv>=dfn[u])
            {
                cut[u]=1;//是割点
                iscut=iscut+1;//割点数加1
                ma[iscut].clear();
                for(;;)
                {
                    Node x=st.top();
                    st.pop();
                    if(wyy[x.u]!=iscut)
                    {
                        ma[iscut].push_back(x.u);
                        wyy[x.u]=iscut;
                    }
                    if(wyy[x.v]!=iscut)
                    {
                        ma[iscut].push_back(x.v);
                        wyy[x.v]=iscut;
                    }
                    if(x.u==u and x.v==v) break;
                }
            }
        } 
        else 
            if(dfn[v]<dfn[u] and v!=fa) 
            {
                st.push(e);
                lowu=min(lowu,dfn[v]);
            }
    }
    if(fa<0 and son==1) cut[u]=0;////如果u是根节点，u有>=2个孩子；u是割点 
    return lowu;
}
inline void found(int x) 
{
    memset(dfn,0,sizeof(dfn));
    memset(cut,0,sizeof(cut));
    memset(wyy,0,sizeof(wyy));
    iscut=0,now=0;
    for ( re int i=1;i<=n;i++ ) 
        if(!dfn[i]) 
            tarjan(i,-1);
}
inline void Init() 
{
    res1=0,res2=1,rt=0,cnt=0;
    memset(head,0,sizeof(head));
}
signed main() 
{
    while(scanf("%d",&n),n) 
    {
        Init();
        for ( re int i=1;i<=n;i++ ) 
        {
            int u=read(),v=read();
            rt=max(rt,u);
            rt=max(rt,v);
            add_edge(u,v);
            add_edge(v,u);//连边
        }
        found(rt);
        for ( re int i=1;i<=iscut;i++ )
        {
            int num=0;
            for ( re int j=0;j<ma[i].size();j++ ) 
            {
//              cout<<cut[ma[i][j]]<<" ";
                if(cut[ma[i][j]]) num+=1;//统计一个强连通分量里割点的数量
            }
            //高能：分类讨论
            if(num>=2) 
            {
                //I can do nothing
            }
            if(num==1) 
            {
                res1=res1+1;
                res2=res2*(ma[i].size()-1);
            }
            if(num==0) 
            {
                res1=res1+2;
            //  cout<<ma[i].size()<<endl;
                res2=res2*(ma[i].size()*(ma[i].size()-1)/2);//C(n,2)
            }
        }
        for ( re int i=1;i<=rt;i++ )
        {
            if(!wyy[i]) res1=res1+1;
        }// 看看那些孤立的点，还没指定属于哪个点双; 
        ++Case;
        printf("Case %d: ",Case);
        printf("%lld %lld\n",res1,res2);
    }
    return 0;
}

这道题目有点难，思维难度比较高，代码细节比较多！但是做完这题，你将获得三倍经验：

经验1：SP16185 BUSINESS - Mining your own business

经验2：UVA1108 Mining Your Own Business

经验3：P3225 [HNOI2012]矿场搭建