P8405 [COCI 2021/2022 #6] Naboj

题目描述

Šikić 先生是一位化学老师，他正在用 $n$ 个金属球和 $m$ 根铜导线做实验。他将一些对金属球用导线相连，使这些球（直接或间接地）与其他球都相连。他想要教学生关于电荷的知识，因此他将通过按顺序给金属球充电来演示它。

Šikić 先生可以让每个球带上正负电荷的一种。当一个金属球带负电荷时，与这个金属球相连的所有导线中的电子都将被排斥到与该导线相连的另一个金属球上。反过来，当一个金属球带正电荷时，与这个金属球相连的所有导线中的电子都将受这个金属球的吸引。无论导线的先前状态如何，给球充电对导线的影响都相同。

在刚上课的时候，所有的金属球都不带电，导线中的电子不动。对于每根导线，Šikić 先生都想让它其中电子的流向是某一个确定的方向。请帮他确定一个给金属球充电的顺序，使得最后电子的流向是他想要的。

输入格式

第一行两个数 $n$ 和 $m$，意义如题目描述。

接下来 $m$ 行每行两个整数 $a_i$ 和 $b_i$，表示金属球 $a_i$ 和 $b_i$ 之间有一根导线相连，并且这根导线中的电子应更靠近 $a_i$ 而不是 $b_i$。在一对金属球之间最多只有一条导线。所有的金属球都通过导线直接或间接相连。

输出格式

如果不可能让最后电子的流向是 Šikić 先生想要的，输出 $-1$。否则输出 $k$，表示需要充电的金属球数量。$k$ 必须小于等于 $2\times 10^5$。

接下来 $k$ 行，每行输出两个整数 $c_i$ 和 $d_i(1\le c_i\le n,0\le d_i\le 1)$，分别表示第 $i$ 步 Šikić 先生需要充电的金属球的编号和是给这个金属球充正电荷（用 $d_i=1$ 表示）还是负电荷（用 $d_i=0$ 表示）。如果有多种方案，输出其中一种即可。

输入输出样例 #1

输入 #1

3 3
1 2
2 3
1 3

输出 #1

3
2 1
3 0
1 1

输入输出样例 #2

输入 #2

4 3
1 2
3 2
2 4

输出 #2

4
2 1
4 0
3 1
1 1

输入输出样例 #3

输入 #3

5 10
2 4
3 4
1 4
4 5
3 2
2 1
5 2
1 3
5 3
1 5

输出 #3

-1

说明/提示

样例解释 1：

首先，我们给金属球 $2$ 充正电荷。金属球 $1,2$ 和金属球 $2,3$ 之间的导线中的电子现在更靠近 $2$。金属球 $1,3$ 之间的导线仍保持中性。

现在我们给金属球 $3$ 充负电荷。金属球 $2,3$ 之间的导线状态不变，金属球 $1,3$ 之间的导线中的电子更靠近金属球 $1$。

最后我们给金属球 $1$ 冲正电荷。金属球 $1,3$ 之间的导线状态不变，但金属球 $1,2$ 之间的导线现在将更靠近金属球 $1$，目标流向达成。

数据范围：

对于全部数据，$1\le n\le 2\times 10^5$，$1\le m\le 5\times 10^5$，$1\le a_i,b_i\le n,a_i\ne b_i$。

本题分值与 COCI 2021-2022#6 分值相同，满分 $110$ 分

C++实现

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=5e5+10;
int n,m,din[N],q[N];
int h[N],e[M],ne[M],idx;
vector<int> ans;
inline void add(int a,int b)
{
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
inline bool topsort(){
	int head=1,tail=0;
	for(int i=1;i<=n;i++)	if(!din[i])	q[++tail]=i;
	while(head<=tail)	{
		int now=q[head++];
		for(int i=h[now];~i;i=ne[i])		{
			din[e[i]]--;
			if(!din[e[i]])
			{
				q[++tail]=e[i];
				ans.push_back(e[i]);			
			}
		}
	}
	return tail==n;
}
int main(){
	memset(h,-1,sizeof h);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)	{
		int u,v;
		scanf("%d%d",&u,&v);
		add(v,u);din[u]++;
	}
	if(!topsort())	puts("-1");
	else	{
		printf("%d\n",(int)ans.size());
		for(auto now:ans)	printf("%d 1\n",now);
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容