舒阳 的博客

舒阳 的博客

QAQ QWQ

题解 P3469 【[POI2008]BLO-Blockade】

posted on 2019-08-15 14:35:20 | under 题解 |

写在前面

这是一道剖析算法本质的题目

关于Tarjan

Tarjan的本质就是一个DFS ——苟新杰老师

既然是DFS,那么在执行的过程中会形成一颗DFS树。 如果这个树点是一个割点,那么思考一下这个点的几个孩子是什么?

Tarjan过程中形成的DFS树,如果这个点是割点,那么这个点的孩子们就是删去这个点后断开的几部分。

为什么?
假设这个点的孩子(子树)分别有SonTree1SonTree2SonTree3
SonTree1SonTree2SonTree3不会属于一个强连通分量。
因为如果这些儿子属于一个强连通分量,那么在遍历第一个儿子(SonTree1)的时候,其他儿子(SonTree2SonTree3)一定能被便利到,而绝对不会成为当前点的子树。

关于本题

两种情况:

  • 如果当前点不是割点,那么删去之后影响不大,只能导致当前被封锁的点到不了其他点,其他点也到不了当前被封锁的点。
  • 如果当前点是割点,那么删去之后会断成几大块儿。对于每一块,到剩下的每一个不属于这一块儿的点都不能继续拜访,设这一块大小为$S$,总点数为$n$,那么这一块儿产生的不能拜访数为:$$Ans += S \times (n - s)$$ 对每一块儿都要这么做。统计答案即可。注意:这个点上面的所有也是一块儿,大小计算方法与求树的重心类似。就是用总点数减去当前点为根的子树大小。

关于代码

/*!
 * FileName: luogu-3469.cpp
 * This Problem is on luogu. The ID of the problem is 3469. 
 * Copyright(c) 2019 Shu_Yu_Mo
 * MIT Licensed
 * Luogu: https://www.luogu.org/space/show?uid=44615
 * Github: https://github.com/oldsuold/
 * Gitee: https://gitee.com/Shu_Yu_Mo/
 * These words were created by an amazing tool on 2019-08-13 08:29:07 written by Shu_Yu_Mo.
 */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstring>
#include<iostream>
#include<cmath>
#include<vector>
#include<queue>
#include<algorithm>
#define inf 0x7fffffff
#define int long long
using namespace std;
const int _N = 110000;
const int _M = 1010000 ;
inline int read()
{
    char c = getchar(); int sign = 1; int x = 0;
    while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); } 
    while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
    return x * sign;
}
int head[_N];
int tot = 0;
struct edges{
    int node;
    int nxt;
}edge[_M];
void add(int u, int v)
{
    edge[++tot].nxt = head[u];
    head[u] = tot;
    edge[tot].node = v;
}
int n, m;
int dfn[_N];
int low[_N];
int dfnClock = 0; 
bool isCut[_N];
int size[_N];
int Ans[_N];
void tarjan(int now, int fa)
{
    low[now] = dfn[now] = ++dfnClock;
    size[now] = 1;
    int child = 0;
    Ans[now] = 0;
    int SumForSon = 0;
    for(register int i = head[now];i;i = edge[i].nxt)
    {
        int exNode = edge[i].node;
        if(dfn[exNode] == 0)
        {
            child ++;
            tarjan(exNode, now);
            size[now] += size[exNode];
            low[now] = min(low[now], low[exNode]);
            if(low[exNode] >= dfn[now])
            {
                SumForSon += size[exNode];
                Ans[now] += (size[exNode] * (n - size[exNode]));
                isCut[now] = true;
            }
        }
        else
            low[now] = min(low[now], dfn[exNode]);
    }
    if(child < 2 && fa < 0) isCut[now] = false;
    if(!isCut[now]) Ans[now] = (n - 1) << 1;
    else Ans[now] += (n - SumForSon - 1) * (SumForSon + 1) + (n - 1);
}

signed main()
{
    n = read(), m = read();
    for(register int i = 1;i <= m;i++)
    {
        int tmpx = read(), tmpy = read();
        add(tmpx, tmpy);
        add(tmpy, tmpx);
    }
    memset(isCut, false, sizeof(isCut));
    tarjan(1, -1);
    for(register int i = 1;i <= n;i++)
            printf("%lld\n", Ans[i]);
    return 0;
}