BZOJ2662-[HNOI2012]矿场搭建(tarjan割点)

题目链接:BZOJ2662-HNOI2012-矿场搭建

题意:

一个无向非连通图,要求每个点的矿工都能走到救援口,可能会把任意一个点ban掉,要求最少的救援口,使得每一个点都能走到救援口,以及最少救援口的方案数。

题解:

首先如果删掉的点不是割点就没有影响。

所以考虑把所以割点删完后,然后每个连通块内可以设一个救援口。

注意两点:

  1. 如果一个块内有两个及多个割点,删掉一个还有其他的割点,所以就不用设救援口。
  2. 如果一个块内没有割点,那么就需要设立两个救援口。

然后至于方案数只需要乘法原理处理一下即可。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM=509;
int m;
struct EDGE
{
    int v,nxt;
} edge[MAXM*2];
int cnt=0,fir[MAXM];
void addedge(int u,int v)
{
    edge[cnt].v=v;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
int tot,rt,deg,dfn[MAXM],low[MAXM];
bool iscut[MAXM];
void tarjan(int u,int F)
{
    dfn[u]=low[u]=++tot;
    for(int i=fir[u]; i!=-1; i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(!dfn[v])
        {
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u])
            {
                if(rt==u)
                    deg++;
                else
                    iscut[u]=1;
            }
        }
        else    if(v!=F)
            low[u]=min(low[u],dfn[v]);
    }
}
int sum,num;
ll sz;
int used[MAXM];
void dfs(int u)
{
    used[u]=sum;
    if(iscut[u])
        return;
    sz++;
    for(int i=fir[u]; i!=-1; i=edge[i].nxt)
    {
        int v=edge[i].v;
        if(iscut[v]&&used[v]!=sum)
        {
            num++;
            used[v]=sum;
        }
        if(!used[v])
            dfs(v);
    }
}
int main()
{
    int cas=0;
    while(scanf("%d",&m)&&m)
    {
        int n=0;
        cnt=tot=0;
        memset(dfn,0,sizeof(dfn));
        memset(low,0,sizeof(low));
        memset(fir,-1,sizeof(fir));
        memset(used,0,sizeof(used));
        memset(iscut,0,sizeof(iscut));
        for(int i=1; i<=m; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            n=max(max(u,v),n);
            addedge(u,v);
            addedge(v,u);
        }
        for(int i=1; i<=n; i++)
        {
            deg=0;
            if(!dfn[i])
            {
                rt=i;
                tarjan(i,i);
            }
            if(deg>=2)
                iscut[i]=1;
        }
        int ans1=0;ll ans2=1;
        sum=0;
        for(int i=1; i<=n; i++)
            if(!used[i]&&!iscut[i])
            {
                ++sum;
                sz=num=0;
                dfs(i);
                if(!num)
                {
                    ans1+=2;
                    ans2*=sz*(sz-1)/2;
                }
                else    if(num==1)
                {
                    ans1++;
                    ans2*=sz;
                }
            }
        printf("Case %d: %d %lld\n",++cas,ans1,ans2);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。