P3225 [HNOI2012]矿场搭建(组合思维+点双连通)

可以说是很好的一道点双连通例题了

$首先考虑对于一个非割点,删去后图分成若干个连通块$

那我们暂时把所有割点删掉,这样分成了若干个连通块

$此时如果在每个连通块建造一个逃生口肯定是符合要求的,但不是最小的$

为什么肯定符合要求呢?

$因为如果坍塌的点是割点,由于每个连通块都有逃生,所以可行$

$坍塌的不是割点,那就是在点双连通中,坍塌后连通块仍然联通,所以可行$

但是答案不是最小的

$首先考虑一个点双连通,没有割点和他相邻$

$那么不可避免地,要放置2个逃生口(被炸了一个还有一个)，逃生口可以随机放置$

$如果只有一个割点和它相邻,那么只需要放1个,但是不能放在割点上$

$因为有割点,说明还有另一个点双和这个割点相邻,放在割点上被炸掉血亏!!$

$而这样如果炸的不是自己逃生口,本点双可以逃生.如果炸的是自己的逃生口$

$那么我可以通过割点去其他点双找出口$

$如果有2个或以上割点相邻,那么不需要设置逃生口了$

$因为不管怎么炸,我都可以通过没被炸掉的割点出去找出口$

#include <bits/stdc++.h> using namespace std; #define int long long const int maxn=5009; struct edge{ int to,nxt,use; }d[maxn]; int head[maxn],cnt; void add(int u,int v){d[++cnt]=(edge){v,head[u],0},head[u]=cnt; } int dfn[maxn],low[maxn],id,vis[maxn],cut[maxn],stac[maxn],top,bccnum; vector<int>bcc[maxn]; int ans1,ans2=1,n,m; void tarjan(int u,int fa) { int child=0; dfn[u]=low[u]=++id, stac[++top]=u; for(int i=head[u];i;i=d[i].nxt ) { int v=d[i].to; if( !dfn[v] ) { tarjan(v,fa); low[u]=min( low[v],low[u] ); if( low[v]>=dfn[u] ) { child++; if( u!=fa||child>=2 ) cut[u]=1; bcc[++bccnum].clear(); /*while( stac[top]!=u ) bcc[bccnum].push_back( stac[top--] );*/ int temp; while( temp=stac[top--] ) { bcc[bccnum].push_back(temp); if( temp==v ) break; } if( stac[top]!=u ) cout << "去死吧\n" << top << endl; bcc[bccnum].push_back(u);//割点不能出栈,因为可能包含在多个点双里 } } else low[u]=min( low[u],dfn[v] ); } } void init() { cnt=1,bccnum=0,id=0,top=0; ans1=0,ans2=1; for(int i=0;i<=n;i++) head[i]=low[i]=dfn[i]=cut[i]=0; n=0; } signed main() { int casenum=0; while( cin >> m && m ) { for(int i=1;i<=m;i++) { int l,r; cin >> l >> r; add(l,r); add(r,l); n=max( max(l,r),n ); } for(int i=1;i<=n;i++) if( !dfn[i] ) tarjan(i,i); for(int i=1;i<=bccnum;i++) { int cu=0,num=bcc[i].size(); for(int j=0;j<num;j++) if( cut[bcc[i][j]] ) cu++; if( !cu ) ans1+=2,ans2*=num*(num-1)/2; if( cu==1 ) ans1++,ans2*=(num-1); } printf("Case %lld: %lld %lld\n",++casenum,ans1,ans2); init(); } }