题解：P5870 [SEERC 2018] Modern Djinn

· · 题解

此题大水。
刚学完随机数就看到了这道题。

解题思路

因为输出任何正确的解都可以（这就是这题水的地方），用随机数来解是正确的，可以完美的符合题目要求的任何正确的解都可以，并且省时省力还省心，所以我们可以随机出每一个愿望是否实现,再枚举每个人是否开心，最后判断能否可行。
题目转化后就是：给每个点黑白染色，然后一条边合法当且仅当起点为黑色，终点为白色，要使得合法边数量大于等于 ⌊M/4⌋+1 。

#include <iostream>//超多的头文件，平时最好不要用万能头 
#include <string>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cstdio>
using namespace std;
#define ll long long//宏定义 
ll n,m,top,A[1000000];
struct yuan//结构体好存数！ 
{
    int x,y;
}B[1000000];
int main()
{
    ll i,j;
    cin >> top;
    while(top--)
    {
        ll sum,step = 0;
        cin >> n >> m;
        for(i = 1;i <= m;i++)
        {
            cin >> B[i].x >> B[i].y;
        }
        sum = 1 + m / 4; 
        while(step < sum)//循环找数 
        {
            for(i = 1;i <= n;i++)
            {
                A[i] = 1 & rand();//选还是不选，这是个问题 
            }
            step = 0;//归零方便下次使用 
            for(i = 1;i <= m;i++)
            {
                if(A[B[i].x] && !A[B[i].y])
                {
                    step++;//符合条件就加一 
                }
            }
        }
        cout << step << endl;
        for(i = 1;i <= m;i++)
        {
            if(A[B[i].x] && !A[B[i].y])
            {
                cout << i << " ";//不要忘了空格 
            }
        }
        cout << endl;//也不要忘了换行 
    }
    return 0;撒花✿✿ヽ(°▽°)ノ✿
}