自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:38:46，当前版本为作者最后更新于2022-11-11 14:51:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接

• 小清新构造题。

• 一开始拿到题可能比较没有头绪，这时有一个小技巧：从特殊情况入手，先看看什么时候无解。

• 我们将一条导线看作一条有向边，边的方向是从离电子远的点到离电子近的点。这时如果你随便在草稿纸上手玩几个样例就会发现：似乎图有环就无解！

• 让我们来严格证明一下这个结论：考虑一个环上最后一个被充电的点，无论我们给它充正电还是负电，它连接的两条边由于需求冲突，都会有一条边在充电后不满足要求。而环上的边只有环上的点能影响，这时我们就推出只要给环上的点充电，就一定不满足要求。而如果不给环上的任意一个点充电，当然也是不合法的，所以结论得证。

• 那此时我们就可以先把环判掉，接下来就是在 $DAG$ 上解决问题。

• 由于是 $DAG$ ，不难想到先将整张图按拓扑序排好，我们按拓扑序顺序考虑每个点，发现与这个点相连的边分为两类：一类是连向之前已经考虑过的点，一类是连向还未考虑的点，前一类边要求这个点充正电，后一类则相反。由于后一类边还有挽救的余地，那对当前点来说，我们当然是先满足前者。

• 于是我们就得到一个策略，按拓扑序给每一个点充正电。

• 让我们证明这个策略的正确性：对于每一条边，一定是它通向的点后考虑，而它通向的点一定会满足它的需求，正确性得证。

• 注意事项：

1. 判环可以在拓扑排序中判定，不需要专门判断。

2. 可能有人会疑惑我有环就无解这个结论只证明了充分性，可实际上后面构造方案时其实就相当于顺便证明了必要性。

• 于是这道题就结束了，下附代码：

#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;
}

• 完结撒花~