题意：
有n个人，每个人的属性值为0或1；m个愿望，x − > y，如果一个愿望被满足的话，说明x的属性值为1,y的属性值为0。要求至少满足m / 4 + 1愿望，输出方案数。
思路：
对于每一个愿望，都有4种方案，只有一种是正确的，概率为1/4
随机赋值0 / 1的话，大概有m / 4个愿望被满足。
跑得飞快。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=2e5+7,maxm=1e6+7,mod=1e9+7; int x[maxn],y[maxn],a[maxn]; int main(){ srand(time(0)); int _=read; while(_--){ int n=read,m=read; for(int i=1;i<=m;i++){ x[i]=read,y[i]=read; } int sum=m/4+1,now=0; while(1){ now=0; for(int i=1;i<=n;i++) a[i]=rand()%2; for(int i=1;i<=m;i++){ if(a[y[i]]==0&&a[x[i]]){ now++; } } if(now>=sum) break; } cout<<now<<endl; for(int i=1;i<=m;i++) if(a[y[i]]==0&&a[x[i]]) cout<<i<<" "; puts(""); } return 0; }
