题解 P3469 【[POI2008]BLO-Blockade】

很好的一道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 可以看到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)