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

· · 题解

这道题的重点就是理解矿点坍塌

我们可以把它理解为不经过这个点以及它所连向的边

就像这道题

理解了这一点之后

再引入一个概念

点双连通分量：

然后这个题就好做了可以做了。

但是要分类讨论！！！

  1. 如果某个点双连通分量里只含有一个原图的割点，那么一旦这个割点坍塌，这个点双连通分量里的人都跑不掉，所以要在这个点双连通分量的除了割点之外的地方设置一个救援出口。

  2. 如果某个点双连通分量里含有两个或更多原图的割点，那么任意一个点坍塌，至少还剩一个割点可以让点双连通分量里的人跑到其他点双连通分量里去，所以这个点双连通分量里不需要设置救援出口。

  3. 设置方法数可以通过乘法原理计算。

总结一下

  1. 先跑出整个图的割点。
void tarjan(int u,int fa)
{
    int child=0;
    low[u]=dfn[u]=++num;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            child++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) isCut[u]=true;
        }
        else
        {
            if(v!=fa&&dfn[v]<dfn[u])
                low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa<0&&child==1) isCut[u]=false;
    return ;
}
  1. 如果这的点没有跑过并且不是割点，那么就进入这个联通块。一个点双连通分量里如果它不是割点那么从它开始搜，搜到割点标记但不走，一定可以遍历这一整个点双连通分量，各位julao可以尝试思考一下手动滑稽
void dfs(int x,int color)
{
    vis[x]=color;
    Fcut++;
    for(int i=0;i<g[x].size();i++)
    {
        int v=g[x][i];
        if(isCut[v]&&vis[v]!=color)
            Cut++,vis[v]=color;
        if(!vis[v])
            dfs(v,color);
    }
    return ;
}
  1. 通过乘法原理计算答案时通过这个联通块里的非割点数量计算。

    但是要分类讨论割点数量！！！

    1. 如果没有割点，那么需要建两个出口，因为要避免一个出口刚好塌掉的情况。
    2. 如果只有一个割点，那么只用建一个在不是割点的地方即可，如果出口塌掉，那么可以通过割点去到另外一个点双里，而且题目也说了同时只有一个矿点出事。
    3. 如果有两个及以上个割点，那么不用设置出口，因为无论如何它都可以跑到另外的点双里去。

注意：n 在输入时求出最大值

附上AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>

using namespace std;

#define int long long

const int MAXX = 500;

int n,m;
int Num,G;
int QAQ,num;
int Fcut,Cut;
int root,count;
int dfn[MAXX+5];
int low[MAXX+5];
int vis[MAXX+5];
bool isCut[MAXX+5];
vector<int> g[MAXX+5];

void Init()
{
    n=0;num=0;
    Num=0;G=1;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(isCut,false,sizeof(isCut));
    for(int i=1;i<=MAXX;i++)
        g[i].clear();
}

void tarjan(int u,int fa)
{
    int child=0;
    low[u]=dfn[u]=++num;
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        if(!dfn[v])
        {
            child++;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]) isCut[u]=true;
        }
        else
        {
            if(v!=fa&&dfn[v]<dfn[u])
                low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa<0&&child==1) isCut[u]=false;
    return ;
}

void dfs(int x,int color)
{
    vis[x]=color;
    Fcut++;
    for(int i=0;i<g[x].size();i++)
    {
        int v=g[x][i];
        if(isCut[v]&&vis[v]!=color)
            Cut++,vis[v]=color;
        if(!vis[v])
            dfs(v,color);
    }
    return ;
}

signed main()
{
    while(scanf("%lld",&m)!=EOF)
    {
        if(m==0) return 0;
        ++QAQ;
        Init();
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%lld %lld",&x,&y);
            n=max(n,max(x,y));
            g[x].push_back(y);
            g[y].push_back(x);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i,-1);
        for(int i=1,color=0;i<=n;i++)
        {
            if(!vis[i]&&!isCut[i])
            {
                ++color;
                Fcut=Cut=0;
                dfs(i,color);
                if(Cut==0)
                    Num+=2,
                    G*=(Fcut-1)*Fcut/2;
                if(Cut==1)
                    Num+=1,
                    G*=Fcut;
            }
        }
        printf("Case %lld: %lld %lld\n",QAQ,Num,G);
    }
    return 0;
}