题解：P11545 [Code+#5] 监控中心

题目大意

给定一个

n

个点

m

条边的无向图，对于

q

组测试数据输出不能与所有点联通的点的个数。

坑点

对于城市 $a_i$ 和 $b_i$ 不一定只有一个情报中心。
在遍历图的过程中可能会因递归堆栈过多爆空间。
有自己指向自己的边，需要筛掉（或者在计算答案的时候直接过滤掉）。

~~吐槽：阅读理解题还给特解样例[○･｀Д´･ ○]~~

分析

因为样例太特殊，所以自己造了组样例，设

u

表示发出信号的点、

v

为被报告的点，下面来分析两种操作。

若 $u$ 是 $v$ 的儿子（因为 $u,v$ 只能是 $a_i$ 或 $b_i$ ，所以不需要并查集来找父亲，但需要考虑上文提到的 $a_i=b_i$ 的情况），则只有 $u$ 的子树（包括自己）符合条件。
若 $v$ 是 $u$ 的儿子，则 $v$ 的子树都不符合条件。

看一组样例：

TXT

对于 3 -1 6 5 这组数据，答案应为

4+1+1=6

。

对于 2 -1 -2 这组数据，显然只有

1

不行，所以答案为

1

。

对于 2 1 2 这组数据，显然只有

1

行，所以答案为

6

。

再看不懂就直接看代码吧：

CPP

#include<bits/stdc++.h>
//#define int long long
#define endl "\n"
#define er puts("")
#define sc putchar(' ')
#define AzureLine return 0
using namespace std;
const int N=25e5+5;
int a[N],b[N],sz[N],fa[N];
vector<int>e[N];
void dfs(int x)
{
	sz[x]=1;//子树算上自己
	for(int i=0;i<e[x].size();i++)
	{
		int y=e[x][i];
		if(fa[y]) continue; //双向边，记得continue
		fa[y]=x;dfs(y);
		sz[x]+=sz[y];
	}
}
int read()
{
	int x=0,a=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar())
		if(c=='-') a=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=x*10+c-'0';
	return x*a;
}
void write(int x)
{
	if(x<0) x*=-1,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
	return;
}
signed main()
{
	int n=read(),m=read();
	for(int i=1;i<=m;i++)
	{
		a[i]=read(),b[i]=read();
		e[a[i]].push_back(b[i]);
		e[b[i]].push_back(a[i]);
	}
	fa[1]=-1;dfs(1);
//	for(int i=1;i<=n;i++) write(sz[i]),sc;
	int q=read();
	while(q--)
	{
		int c=read(),ans=0;//多测清空
		for(int i=1;i<=c;i++)
		{
			int x=read(),u,v;
			if(x>0) u=a[x],v=b[x];
			else u=b[-x],v=a[-x];
			if(u==fa[v]) ans+=sz[v];
			if(v==fa[u]) ans-=sz[u];
		}
		write(ans>=0?ans:ans+n),er;//如果ans为负，那显然是应为求的是合适的点，所以加n
	}
	return 0;
}

题解：P11545 [Code+#5] 监控中心

文章操作

题目大意

坑点

分析

相关推荐

评论

题解：P11545 [Code+#5] 监控中心