M_sea

洛谷3469 [POI2008]BLO-Blockade
题目描述在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口,尽管可能有桥,隧道或者高...
扫描右侧二维码阅读全文
22
2018/08

洛谷3469 [POI2008]BLO-Blockade

题目描述

在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口,尽管可能有桥,隧道或者高架公路(反正不考虑这些)。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民,他们被孤独所困扰。事实证明,每个公民都想拜访其他所有公民一次(在主人所在的城镇)。所以,一共会有n*(n-1)次拜访。

不幸的是,一个程序员总罢工正在进行中,那些程序员迫切要求购买某个软件。

作为抗议行动,程序员们计划封锁一些城镇,阻止人们进入,离开或者路过那里。

正如我们所说,他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序:

读入Byteotia的道路系统,对于每个被决定的城镇,如果它被封锁,有多少访问不会发生,输出结果。

传送门

算法

封锁一个城镇$\to$断掉一个点$\to$割点。

我们尝试从样例找规律。发现非割点答案都是$8$,即$2(n-1)$。

这个很容易想到,因为断掉这个点后减少的只有出去的$n-1$条和进来的$n-1$条。


对于割点,应该怎么搞呢。。。

上图:

emmm.png

显然红点是割点。

那么它被断掉后,就会有$2\times (8-1)+1\times 6+3\times 4+3\times 4=44$条路被断掉。

这个根据乘法原理和加法原理也很容易得到。

那么统计一下子树大小即可。

问题是我判联通有点问题,所以用了题解里的另一种方式。

原内容:假如$i$是割点,那么会把图分为$a$个连通块以及$i$本身,由于Tarjan在求割点的过程中是一棵搜索树往下遍历,所以除了它和它的子树外,还会有其他剩余点共同构成另一个连通块(有点类似树的重心的求法)。

这个描述很清楚,只是我不太理解

而且这样统计不会有奇怪的问题。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int min_(int a,int b) { if (a<b) return a; else return b; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int n,m;

struct Edge { int v,nxt; };
Edge e[1000010];
int head[100010],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int dfn[100010],low[100010];
bool cut[100010];
int sz[100010],ans[100010];
int dfs_clock=0;

inline void Tarjan(int u,int root) {
    sz[u]=1; dfn[u]=low[u]=++dfs_clock;
    int f=0,sum=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (!dfn[v]) {
            Tarjan(v,root); sz[u]+=sz[v];
            low[u]=min_(low[u],low[v]);
            if (low[v]>=dfn[u]) {
                f++,sum+=sz[v]; ans[u]+=sz[v]*(n-sz[v]);
                if (u!=root||f>1) cut[u]=1;
            }
        }
        else low[u]=min_(low[u],dfn[v]);
    }
    ans[u]+=(n-sum-1)*(sum+1)+(n-1);
}
            
mainint main() {
    n=read(),m=read();
    for (re int i=1;i<=m;i++) {
        int x=read(),y=read();
        addEdge(x,y);
        addEdge(y,x);
    }
    for (re int i=1;i<=n;i++)
        if (!dfn[i]) Tarjan(i,i);
    for (re int i=1;i<=n;i++) {
        if (!cut[i]) printf("%lld\n",2*(n-1));
        else printf("%lld\n",ans[i]);
    }
    return 0;
}
最后修改:2018 年 11 月 09 日 05 : 19 PM

发表评论