【tarjan】【连通图】P3225 [HNOI2012]矿场搭建
wjyyy
2018-06-08 08:41:45
矿点坍塌我们可以抽象为将这个点删去。设图中原来有k个联通块,如果删掉割点,那么现在就有了k+1个联通块,如果不是割点,联通块数目不变。因此我们可以看出,割去任一个割点,割点两边的联通块都需要设一个逃生口。(关于[怎么求割点](http://www.wjyyy.top/))我们先来分析几个情况:
### 1.链上
![这是一条链](http://www.wjyyy.top/wp-content/uploads/2018/06/QQ截图20180608080620.png)
可以看出,图中有5个割点:2,3,4,5,6。如果不是割点的点坍塌了,例如1,那么只要在2-7中任意设置一个即可。但如果是割点坍塌了,两边的人只能往两头跑,而我们看到,在上图中,只要设置两个点:一头一尾的逃生出口,就可以满足任何坍塌情况。
### 2.环
如果在一个环上,每两个点都可以互相直达,那么我们可以设置任一个点作为逃生出口,即可满足其他所有点到达这个地方。但是要考虑逃生出口坍塌的情况,所以一个环上要设置两个逃生出口,可以使无论逃生出口是否坍塌,都有一个逃生出口可用。n个点中任选两个点,方案数是$C^2_n =\frac{n(n-1)}{2}$
### 3.一般情况
割点会分整个图为多个双连通分量,我们将每个双联通分量看作整个联通块,那么一个双连通分量中只需要设置一个点,就可以满足这个分量里的点能够跑到这个出口来。同上,我们还要考虑出口坍塌的情况。在这里,因为只会坍塌一个点,所以如果出口坍塌了,割点就不会坍塌,这个分量中的其他点可以通过割点跑到另外的双连通分量中,此时等价于同一个双连通分量。我们可以继续将这些点抽象为一个概念:叶子连通块。
### 4.叶子连通块
叶子节点是没有出度的点,入度为1,也就是只连了一条边。那么叶子连通块的概念就是:只连接了一个割点的双连通分量。 同时,对于连接两个割点的双连通分量,其中一个割点坍塌,那么另一个割点就不会坍塌,可以通过另一个割点合并到另外一个双连通分量中。而叶子连通块就不行了,如果叶子连通块的割点(叶子的父亲)被切断,那么它就是一个单独的连通块,所以这里一定要设置一个逃生出口。在这里设置一个逃生出口,有weight种选择(weight是节点数)。根据乘法原理,最小个数是叶子连通块的个数;总方案数是所有叶子连通块的weight之积。
所以我们只需要判断一个连通块dfs后是否只找到一个割点(用del数组存起来)
Code:
```pascal
#include<iostream>
#include<cstring>
#include<cstdio>
using std::min;
using std::max;
using std::cin;
using std::cout;
struct node
{
int n;
node *nxt;
node(int n)
{
this->n=n;
nxt=NULL;
}
node()
{
nxt=NULL;
}
};
node head[550],*tail[550];
int dfn[550],low[550],cnt=0;//tarjan核心数组
int n,m;
bool del[550];
void tarjan(int x,int from)//求割点数
{
int son=0;
dfn[x]=++cnt;
low[x]=dfn[x];
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(dfn[p->n])
low[x]=min(low[x],dfn[p->n]);
else
{
son++;
tarjan(p->n,x);
low[x]=min(low[x],low[p->n]);
if(from!=0&&low[p->n]>=dfn[x])
del[x]=true;//del=true就是割点
if(from==0&&son>1)
del[x]=true;
}
}
}
bool app[550];//是否出现过,判断一共有多少个点
unsigned long long sum=0;//sum<1<<64
int num=0,w=0;
bool used[550];
bool flag;
void dfs(int x)//判断是否为叶子连通块
{
w++;//子节点个数
node *p=&head[x];
while(p->nxt!=NULL)
{
p=p->nxt;
if(used[p->n])//遍历过的点或出发割点
continue;
if(del[p->n])//找到另一个非出发割点的割点,说明不是叶子连通块
{
flag=true;
continue;
}
used[p->n]=true;
dfs(p->n);
}
return;
}
int main()
{
int u,v,t=0;
scanf("%d",&m);
while(m!=0)
{
t++;
cnt=0;
n=0;
num=0;
sum=1;
memset(app,0,sizeof(app));
memset(del,0,sizeof(del));
memset(dfn,0,sizeof(dfn));
memset(used,0,sizeof(used));
for(int i=1;i<=544;i++)//最多500个点
tail[i]=&head[i];
for(int i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
app[u]=true;
app[v]=true;
if(u>n)
n=u;
if(v>n)
n=v;
tail[u]->nxt=new node(v);
tail[u]=tail[u]->nxt;
tail[v]->nxt=new node(u);
tail[v]=tail[v]->nxt;
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i,0);
for(int i=1;i<=n;i++)
if(del[i]&&app[i])
{
used[i]=true;
node *p=&head[i];
while(p->nxt!=NULL)
{
p=p->nxt;
if(!del[p->n]&&!used[p->n])
{
w=0;
used[p->n]=true;
flag=0;
dfs(p->n);
if(!flag)//乘法原理
{
num++;//联通块个数
sum*=w;//方案个数
}
}
}
used[i]=false;//
}
if(num==0)//如果没有割点
{
num=2;
if(n-1==m)
sum=2;
else
sum=n*(n-1)/2;//加法原理
}
printf("Case %d: %d ",t,num);
cout<<sum<<std::endl;
scanf("%d",&m);
}
return 0;
}
```
注:这个题给出的图应该是连通图,不然如果一个矿场有两个矿区,比如两个不相交的环,就需要对每个环单独乘一次,这里没有考虑。