题解：P5870 [SEERC 2018] Modern Djinn

此题正确题面。

这道题很明显可以使用随机化实现。

随机第 \(i\) 个人的心情为 \(mood_i\)，是 \(1\) 的时候心情好，\(0\) 的时候心情不好。代码就像下面这样：

for (int i = 1; i <= n; i++) {mood[i] = rand() & 1;
}

然后判断这时候可以实现多少个人的愿望：

int cnt = 0;
for (int i = 1; i <= m; i++) {if (mood[x[i]] && !mood[y[i]]) {++cnt;}
}

当 \(cnt \geq \lfloor m/4 \rfloor +1\) 的时候输出答案：

if (cnt >= m / 4 + 1) {printf("%d\n" ,cnt);for (int i = 1; i <= m; i++) {if (mood[x[i]] && !mood[y[i]]) {printf("%d " , i);}}puts("");break;
}

但如果 \(cnt < \lfloor m/4 \rfloor +1\)，那么就重复之前的步骤，随机人的心情。

完整 AC 代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 100000 + 5;
const int M = 200000 + 5;
int n, m;
int x[M], y[M];
bool mood[N];
int qcin()
{int t=0,f=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-'){f=-1;}c=getchar();}while(c>='0' && c<='9'){t=t*10+c-'0';c=getchar();}return t*f;
}
signed main() {srand(72183);int T=qcin();while (T--) {n=qcin();m=qcin();for (int i = 1; i <= m; i++) {x[i]=qcin();y[i]=qcin();}while (true) {for (int i = 1; i <= n; i++) {mood[i] = rand() & 1;}int cnt = 0;for (int i = 1; i <= m; i++) {if (mood[x[i]] && !mood[y[i]]) {++cnt;}}if (cnt >= m / 4 + 1) {printf("%d\n" ,cnt);for (int i = 1; i <= m; i++) {if (mood[x[i]] && !mood[y[i]]) {printf("%d " , i);}}puts("");break;}}}return 0;
}