自动搬运

查看原文

来自洛谷，原作者为

	Imakf **

搬运于2025-08-24 22:15:07，当前版本为作者最后更新于2020-07-11 17:40:22，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先这题题面有点问题，应该是：给每个点黑白染色，然后一条边合法当且仅当起点为黑色，终点为白色。 使得合法边数量 $\ge \left\lfloor \dfrac{m}{4}\right\rfloor + 1$

感性理解一下此题随机化为何可以通过。

对于每一条边两个连接的两个点，只有一种染色方法是正确的，正确率为 $\frac{1}{4}$。

也就是我们随机染色，期望 $\frac{m}{4}$ 条愿望被满足。（注意期望并不一定大于中位数）

我也不知道为什么期望这么多，实际上也跑得这么快。

#include <bits/stdc++.h>

int read(){
	char k = getchar(); int x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9')
		x = x * 10 + k - '0' ,k = getchar();
	return x;
}
const int MX = 200000 + 23;
int u[MX] ,v[MX] ,ok[MX];
void solve(){
	int n = read() ,m = read();
	int need = m / 4 + 1;
	for(int i = 1 ; i <= m ; ++i)
		u[i] = read() ,v[i] = read();
	while(1){
		for(int i = 1 ; i <= n ; ++i)
			ok[i] = rand() & 1;
		int cnt = 0;
		for(int i = 1 ; i <= m ; ++i)
			if(ok[u[i]] && !ok[v[i]]) ++cnt;
		if(cnt >= need){
			printf("%d\n" ,cnt);
			for(int i = 1 ; i <= m ; ++i)
				if(ok[u[i]] && !ok[v[i]]) printf("%d " ,i);
			puts("");
			break;
		}
	}
}

int main(){
	int T = read();
	while(T--) solve();
	return 0;
}