【BZOJ2730】[HNOI2012]矿场搭建

2015.08.03 13:54 Mon | 23次阅读 | 旧日oi | 固定链接 | 源码

题目大意

给出一幅连通的无向图,求至少需要给多少个点染色,使得任意一个点坏掉后每个点都能到达一个黑点,并求出方案数。
n<=500(事实上开到50000都没事)

题解

把每个双连通分量搞出来。
首先,如果只有一点双连通分量,那么至少需要2个点,共n*(n-1)/2种放法、
如果不只一个点双连通分量:考虑每个双连通分量里有几个割点,如果只有一个,那么这个双连通分量里必须要放一个,如果不止一个,那么就不用放了。
这么说有点抽象。形象点来说,求出双连通分量缩点后,形成了一颗树结构,只有度数为1的节点(和度数为1的根)必须要放(并且不能放到割点上,要不然断掉割点还是不满足题意。),度数>1的节点的话至少有两条不同的路到达度数为1的点。、

我的程序

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;
#define N 505
struct edge
{
    int to,next;
}e[N<<1];
int h[N],tp;
void ae(int u,int v)
{
    e[++tp].to=v;
    e[tp].next=h[u];
    h[u]=tp;
}
int n,tim,bcc_cnt;
long long ans1,ans2;
vector<int> bcc[N];
int dfn[N],low[N],bccno[N];
bool iscut[N];
struct node
{
    int u,v;
    node(int a=0,int b=0):u(a),v(b){}
};
stack<node> st;
void dfs(int u,int fa)
{
    dfn[u]=low[u]=++tim;
    int son=0;
    for(int v,i=h[u];e[i].to;i=e[i].next)
    {
        v=e[i].to;
        node ed=node(u,v);
        if(!dfn[v])
        {
            st.push(ed);son++;
            dfs(v,u);
            low[u]=min(low[v],low[u]);
            if(low[v]>=dfn[u])
            {
                iscut[u]=1;
                bcc_cnt++;
                for(;;)
                {
                    node x=st.top();st.pop();
                    if(bccno[x.u]!=bcc_cnt) bccno[x.u]=bcc_cnt,bcc[bcc_cnt].push_back(x.u);
                    if(bccno[x.v]!=bcc_cnt) bccno[x.v]=bcc_cnt,bcc[bcc_cnt].push_back(x.v);
                    if(x.u==u&&x.v==v) break;
                }
            }
        }
        else if(dfn[v]<dfn[u]&&v!=fa)
        {
            st.push(ed);
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(fa<0&&son==1) iscut[u]=0;
}
void find_bcc()
{
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(bccno,0,sizeof(bccno));
    for(int i=1;i<=bcc_cnt;i++) bcc[i].clear();
    bcc_cnt=tim=0;
    while(!st.empty()) st.pop();
    dfs(1,-1);
}
int main()
{
    freopen("mining.in", "r", stdin);
    freopen("mining.out", "w", stdout);
    int T=0;
    while(cin>>n&&n)
    {
        memset(h,0,sizeof(h));tp=0;
        memset(iscut,0,sizeof(iscut));
        ans1=0,ans2=1;
        for(int u,v,i=1;i<=n;i++)
        {
            scanf("%d%d",&u,&v);
            ae(u,v);ae(v,u);
        }
        find_bcc();
        for(int tmp,i=1;i<=bcc_cnt;i++)
        {
            tmp=0;
            for(int j=0;j<bcc[i].size();j++)
            if(iscut[bcc[i][j]]) tmp++;
            if(tmp==1) ans1++,ans2*=(bcc[i].size()-1);
        }
        if(bcc_cnt==1) ans1=2,ans2=bcc[1].size()*(bcc[1].size()-1)/2;
        T++;cout<<"Case "<<T<<": ";cout<<ans1<<" "<<ans2<<endl;
    }
}```