题意:
一个无向非连通图,要求每个点的矿工都能走到救援口,可能会把任意一个点ban掉,要求最少的救援口,使得每一个点都能走到救援口,以及最少救援口的方案数。
题解:
首先如果删掉的点不是割点就没有影响。
所以考虑把所以割点删完后,然后每个连通块内可以设一个救援口。
注意两点:
- 如果一个块内有两个及多个割点,删掉一个还有其他的割点,所以就不用设救援口。
- 如果一个块内没有割点,那么就需要设立两个救援口。
然后至于方案数只需要乘法原理处理一下即可。
参考代码:
#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;
}