ID_8483 修建围栏

经验分享区
1

这是一道并查集的应用题，不过我用的是 dfs（怎么 又是 dfs，并查集怎么你了）

解题思路

若牛 u 和牛 v 相互哞叫，则在节点 u 和节点 v 之间建一条无向边

然后遍历每一个节点，对于第 i 的节点

1.节点 i 没有被遍历过，那么我们就 dfs 之，找到直接或间接与节点 i 相连的节点中 x 、 y 坐标的最大值和最小值，然后更新 ans = min(ans, 2 * (maxx - minx + maxy - miny));

2.节点 i 被遍历过，跳过

最后输出 ans 即可

代码

dfs遍历

void dfs(int u)//dfs并找 x 、 y 坐标的最大值和最小值
{
	for(int i = 0; i < e[u].size(); i++)
	{
		int v = e[u][i];
		if(!b[v])
		{
			b[v] = 1;
			maxx = max(maxx, a[v].x);
			maxy = max(maxy, a[v].y);
			minx = min(minx, a[v].x);
			miny = min(miny, a[v].y);
			dfs(v);
		}
	}
}

遍历每个节点

for(int i = 1; i <= n; i++)//dfs每个未被遍历的节点
	if(!b[i])
	{
		b[i] = 1;
		maxx = minx = a[i].x;
		maxy = miny = a[i].y;
		dfs(i);
		ans = min((maxx - minx + maxy - miny) * 2, ans);//更新ans
	}
1 个赞