【图论·习题】三角形灯阵

Problem

题目描述

中秋节的晚上，小x在桌面上放了许多好看的彩灯。遗憾的是，这些彩灯可能并非全部都亮着。于是，小x打算把全部这些彩灯都点亮。

但是，小x很快发现，这些彩灯的摆放是非常有规律的，事实上，彩灯的位置都在平面的正三角形镶嵌的某个交点处。距离为单位长度的彩灯被认为相互相邻。可以看出，每个彩灯最多与六个彩灯相邻，相邻的彩灯都在以其为中心的单位正六边形的顶点上。

下图就是一种合法的彩灯摆放（对应样例数据）：

【图论·习题】三角形灯阵

其中，实心和空心的圆点分别代表亮与灭的彩灯，实线边代表彩灯间的相邻关系。

图中的边组成了若干单位正三角形（边长为单位长度的三角形），可以看出，每个彩灯与它相邻的彩灯最多可以组成六个单位正三角形。而所有的单位三角形可被分成两类，我们称为 A 类以及 B 类，图中加阴影的三角形属于 A 类。A 类三角形的特征是，三个顶点分别在上方、左下方及右下方。

每个 A 类三角形中有一个开关（图中未画出），按动三角形中的开关开关会改变三个顶点上每个彩灯的亮灭状态（亮变成灭，灭变成亮）。

那么，要点亮所有彩灯，最少需要按动多少次开关呢？

输入格式

输入数据描述了每个彩灯的初始亮灭状态以及所有三角形。

第一行一个整数 N，表示彩灯的数目，彩灯被编号为 1 至 N。

第二行 N 个 0 或 1 的整数，第 i 个 0 或 1 表示第 i 个彩灯初始的状态是灭或亮。第三行一个整数 M，表示有 M 对彩灯相邻的关系。

以下 M 行，每行三个整数，表示一对彩灯相邻的关系。前两个整数即相邻的这一对彩灯的编号。第三个整数表示第二个彩灯相对于第一个彩灯的方位，0~5 分别表示右方、右下、左下、左方、左上、右上。

例如，“1 3 1”表示“第 3 个彩灯在第 1 个彩灯的右下方”。

输出格式

如果不可能做到点亮所有彩灯，输出-1，否则输出最小的步数。

题解

B类三角形暂且不管，考虑A类三角形对答案的影响。

对于A类三角形的顶点，若它不是另一个A类三角形下面的两个点，即只有一个A类三角形其亮暗则：

若这个三角形是亮的，则这个三角形一定不能够改变；因为改变只会让亮着的三角形变暗，且没有其它的三角形使其重新变亮。
若这个三角形是暗的，则这个三角形必须要改变；因为只有这个三角形能让当前灯变亮。

因此我们就通过寻找每一个仅在一个A类三角形中的点，来寻找点和点之间的依赖关系：

若当前点进行操作后，当前点必然对下面的三角形产生影响，且这个点明显可以忽略不计；即删去这个点对下面两个点的关系。此时若下面的两个点也像这样成为了一个唯一三角形的顶点，也向这样有了唯一的解决方案。

这种方式就是一个拓扑排序。

找到每一个仅在一个A类三角形且是顶点的点，则这个点就是那个拓扑排序中入度为0的点，然后一边做拓扑排序一边进行操作，不断找到那个仅有A类顶点的点即可。

然后我们就有一个问题就是如何建图来完成这个关系：

向左或者向右的点对答案不存在影响，不管。
x的左下或右下有y，则x→y。
x的左上或右上有y，则y→x。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;
int s[60000];
int in[60000];
queue<int>q;
vector<int>a[60000]; 
int main(void)
{
	freopen("triangle.in","r",stdin);
	freopen("triangle.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i) scanf("%d",s+i);
	scanf("%d",&m);
	for (int i=1,x,y,z;i<=m;++i)
	{
		scanf("%d %d %d",&x,&y,&z);
		if (z==1 || z==2) a[x].push_back(y),in[y]++;
		if (z==4 || z==5) a[y].push_back(x),in[x]++;
	}
	for (int i=1;i<=n;++i) 
	    if (!in[i]) q.push(i);
	while (q.size())
	{
		int now=q.front();
		q.pop();
		for (int i=0;i<a[now].size();++i)
		{
			int next=a[now][i];
			in[next]--;
			if (!in[next]) q.push(next);
			if (!s[now]) s[next]^=1;
		}
		if (!s[now]) ans++;
	}
	printf("%d\n",ans);
	return 0;
}

【图论·习题】三角形灯阵

Problem

题解

相关推荐