• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

P3469 [POI2008]BLO-Blockade 题解

admin

11月 28, 2021

题目大意

P3469 [POI2008]BLO-Blockade

给出一张无向图,要求输出分别删除某个点相连的边后,无向图中有多少个有序点对满足(x)(y)不连通

问题求解

删掉一个点是否连通,自然而然就想到了割点,如果这个点是割点,那么删掉边后其他(n-1)的点都是连通的,由于是有序点对,所以这个点的答案就是(2 imes (n-1))

对于不是割点的点,需要求出删除后各连通块的大小,相乘的和就是答案,然后思考如何快速求出,在搜索树上,节点(i)的子节点集合中,有(t)个点(s_1,s_2,…,s_k)满足割点判定条件,(dfn[i]≤low[s_k]),于是,删除(i)关联的所有边后,无向图会分成至多(t+2)个连通块因为

  • 节点(i)自身是一个连通块

  • (t)个连通快,分别由搜索树上以(s_k(1≤k≤t))为根的子数中的节点构成

  • 还可能有一个连通块,除了由上述节点之外的所有节点构成

所以记下搜索树中子树的大小(size[x]),显然答案就表示成

[sum_{i=1}^t{size[s_i] imes(n-size[s_i])}+1 imes(n-1)+(n-1-sum_{i=1}^t{size[s_k]}) imes(1+sum_{i=1}^t{size[s_k]})
]

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int maxn=100005,maxe=1000005;
int lnk[maxn],nxt[maxe],son[maxe],cnt=1,num;
int dfn[maxn],low[maxn],size[maxn];
int N,M;
LL Ans[maxn];
bool cut[maxn];

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
	while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void add_e(int x,int y){son[++cnt]=y;nxt[cnt]=lnk[x];lnk[x]=cnt;}
void tarjan(int x){
	dfn[x]=low[x]=++num;size[x]=1;
	int flg=0,sum=0;
	for(int j=lnk[x];j;j=nxt[j]){
		if(!dfn[son[j]]){
			tarjan(son[j]);
			size[x]+=size[son[j]];
			low[x]=min(low[x],low[son[j]]);
			if(dfn[x]<=low[son[j]]){
				flg++;
				Ans[x]+=(LL)size[son[j]]*(N-size[son[j]]);
				sum+=size[son[j]];
				if(x!=1||flg>1)cut[x]=1;
			}
		}
		else low[x]=min(low[x],dfn[son[j]]);
	}
	if(cut[x])
		Ans[x]+=(LL)(N-sum-1)*(sum+1)+(N-1);
	else
		Ans[x]=2*(N-1);
}
int main(){
	freopen("P3469.in","r",stdin);
	freopen("P3469.out","w",stdout);
	N=read();M=read();
	for(int i=1;i<=M;i++){
		int x=read(),y=read();
		if(x==y)continue;
		add_e(x,y);add_e(y,x);
	}
	tarjan(1);
	for(int i=1;i<=N;i++)
		printf("%lld
",Ans[i]);
	return 0;
}

发表评论

您的电子邮箱地址不会被公开。