P3225 [HNOI2012]矿场搭建
斯德哥尔摩
2018-08-01 21:36:46
[P3225 [HNOI2012]矿场搭建](https://www.luogu.org/problemnew/show/P3225)
思路：找出割点和所有的双连通分量，然后统计每个双连通分量里的个点的个数分情况讨论。
1. 若该连通分量里有不少于两个割点，则它是安全的，因为无论哪个割点炸了，里面的点可以通过其他的没炸的割点跑到其他的双连通分量里去。
2. 若该连通分量里只有一个割点，那么如果这个割点炸了，则里面的点就不可能跑到其他的双连通分量里去了，所以要在这个割点里建一个出口。
3. 若该连通分量里一个割点也没有，说明它与外界完全不连通，这时如果只建一个出口的话，那么如果这个出口炸了就$GG$，所以还需要另一个出口“以防万一”（即建两个出口）
对于方案数的话，我们发现如果要建出口的话，该双连通分量里的任何一个非割点的节点都是可以的，因此用一下组合数学就可以搞定了。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 510
using namespace std;
int n,m,c,d,num,times,size;
long long ans,sum;
int head[MAXN],deep[MAXN],low[MAXN],fa[MAXN],vis[MAXN];
bool flag[MAXN];
struct Graph{
int next,to;
}a[MAXN<<1];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add(int x,int y){
a[c].to=y;a[c].next=head[x];head[x]=c++;
a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int x){
int s=0;
deep[x]=low[x]=d++;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(!deep[v]){
fa[v]=fa[x];
dfs(v);
low[x]=min(low[x],low[v]);
if(low[v]>=deep[x]&&x!=fa[x])flag[x]=true;
if(x==fa[x])s++;
}
low[x]=min(low[x],deep[v]);
}
if(x==fa[x]&&s>=2)flag[fa[x]]=true;
}
void answer(int x){
size++;
vis[x]=times;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(vis[v]!=times&&flag[v]){
num++;
vis[v]=times;
}
if(!vis[v]&&!flag[v])answer(v);
}
}
void work(){
for(int i=1;i<=n;i++)
if(!vis[i]&&!flag[i]){
size=num=0;
times++;
answer(i);
if(num==0){ans+=2;sum*=size*(size-1)/2;}
if(num==1){ans++;sum*=size;}
}
printf("%lld %lld\n",ans,sum);
}
void init(){
c=d=sum=1;
n=times=ans=0;
memset(head,0,sizeof(head));
memset(deep,0,sizeof(deep));
memset(low,0,sizeof(low));
memset(flag,false,sizeof(flag));
memset(vis,0,sizeof(vis));
int x,y;
for(int i=1;i<=m;i++){
x=read();y=read();
n=max(n,max(x,y));
add(x,y);
}
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)if(!deep[i])dfs(i);
}
int main(){
for(int cases=1;;cases++){
m=read();
if(m==0)break;
printf("Case %d: ",cases);
init();
work();
}
return 0;
}
```