题解 P5870 【[SEERC2018]Modern Djinn】

· · 题解

首先这题题面有点问题，应该是：给每个点黑白染色，然后一条边合法当且仅当起点为黑色，终点为白色。 使得合法边数量 \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;
}