题解 P3469 【[POI2008]BLO-Blockade】
command_block
2018-12-27 20:01:08
很好的一道tarjan题啊。
看到题面就知道是**缩点双联通分量**就或者**找割点**了。
至于上述两个东西如处理,请右转[模板区](https://www.luogu.org/problemnew/show/P3388)
**缩点双联通分量**或**找割点**都可以解决本题。
两者其实本质是一样的,区别就在于前者常数大,码量大,思想复杂,没有很好的**利用$tarjan$算法的性质**。
所以我们来讲利用割点来求解的(~~复杂度严格O(n+m)的~~)算法。
假如您封锁一个城镇,可以视为把所有与这个点相关的边都断开(也就是**阻止人们进入,离开或者路过那里**)。
这样的话,必然把图分成几部分,这这些部分的大小设为$\Large{c_1,c_2,c_3...c_n}$。
比如说这张图(谁知道出处?)
![](http://img.blog.csdn.net/20130505212216043)
http://img.blog.csdn.net/20130505212216043
可以看到47节点被封锁之后整个图变为了四部分。
那么,对于第i堆的所有人,访问其他堆的愿望都不能满足,访问自己人还是可以的。
所以第i堆的贡献为$\Large{c_i(n(\text{所有c的总和})-c_i})$
怎么知道每个点的$\Large{c}$数组呢?$tarjan$算法可以做到。
```
别小看dfs.
——算法导论
```
$tarjan$这个算法有很多的优秀性质。
求割点的时候,利用了$\large{low[sun]<=dfn[u]}$这个判别,这个判别的意思就是:这个子树中的所有节点都跑不出割点的魔掌,被分割了出去。
也就是说相当于一堆。(不懂看代码)
把这些堆都求出来了之后,别忘记:
1.这个点本身也算一堆。
2.除此之外剩下的都算一堆。
这个算法虽然每个节点的${total_c}$不同,但是${total_c}$的总量为$O(m)$所以复杂度正确。
**P.S** long long要开足!!WA·80-90的注意一下
Code:
```cpp
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> g[100500];
int n,m,from,to,tim,
dfn[100500],low[100500];
long long c[100500],ans[100500];
void dfs(int num,int fa)
{
low[num]=dfn[num]=++tim;
ans[num]=0;c[num]=1;
long long tmp=1;//自己在自己的子树中
//tmp: 子树节点和
for (int i=0,v;i<g[num].size();i++)
if (!dfn[v=g[num][i]]){
dfs(v,num);
c[num]+=c[v];
low[num]=min(low[num],low[v]);
if (low[v]>=dfn[num]){
ans[num]+=c[v]*((long long)n-c[v]);
tmp+=c[v];//某个可以被阻断的子树
}
}else if (g[num][i]!=fa)
low[num]=min(low[num],dfn[v]);
ans[num]+=1*(n-1);//算这个点本身成一块
ans[num]+=((long long)n-tmp)*tmp;//剩下不在dfs搜索树字树中的
}
void t(int root)
{
//对根的特殊处理,类似上面
low[root]=dfn[root]=++tim;
ans[root]=0;
int tmp=0;
for (int i=0,v;i<g[root].size();i++)
if (!dfn[v=g[root][i]])
{tmp++;dfs(v,root);ans[root]+=((long long)n-c[v])*c[v];}
ans[root]+=1*(n-1);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=m;i++){
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}t(1);
for (int i=1;i<=n;i++)
printf("%lld\n",ans[i]);
}
```
[AC记录](https://www.luogu.org/recordnew/show/15031747)