.gitignore

*.out

README.md

圖上賽局

main.cpp

#include <bits/stdc++.h>
using namespace std;

const int N = 100;

bitset<N> G[N];

void input(){
    for (int i=0; i<N; i++){
        cin >> G[i];
        G[i][i] = 1;
    }
}

void dfs(int deep, bitset<N> &first, bitset<N> &second){
    if (deep==0)return;

    bitset<N> alive = bitset<N>().set() ^ (first|second);

    bitset<N> best_first, best_second;
    bool found=0;

    for (int i=0; i<N; i++) if (alive[i]){
        bitset<N> nfirst = first | G[i];
        bitset<N> nsecond = (bitset<N>().set() ^ nfirst) & second;
        dfs(deep-1,nsecond,nfirst);
        if ( !found || nfirst.count()-nsecond.count() > best_first.count()-best_second.count() ){
            best_first = nfirst;
            best_second = nsecond;
            found = 1;
        }
    }
    first = best_first;
    second = best_second;
}

int main(){
    input();

    bitset<N> first, second;
    dfs(6,first,second);
    cout <<  first.count() << endl <<  first << endl;
    cout << second.count() << endl << second << endl;;
}

main_1.in

0000000000000000000100000000000010000000000000000000000010000000000000000000010000000111000000000000
0010000000000000001000000000001000000000000000000100000000100100100000000000000000000000000000000000
0100001000010000000000000000000000000100000010000000000000000000010010000000000100000001000000000000
0000100000000101000000000000000100000000000000000000000000000000000000000000000000000000000000000000
0001010010000000000001000000000100100000000000000000000000000101000000011000000000000000000000000000
0000100000000000000000100000001000000000000010000000000000000000000000000000100010000000000000000010
0010000000000010000000000000000000000000000000000000100000000000000000000000000010010000000000000000
0000000000000000000000000000010000000100000000000000000000000000000000100000000000000000010000000101
0000100000000000000000000001010000000000000000000000000011000000000000000000000001000000000011000000
0000000000000000000000010000000001010100000000000000000000000000000000000000100000000000100000000000
0000000000000000000000000000000000000000000010000100001000000000000000000010000000000000000000000001
0010000000001100000000000000000000000000000000000000000000000010000000000000000000000000000000000100
0000000000010010000100000000000000010000000000000001000000001000000000010000000000000000000000000000
0001000000010001000000000000000000000000000000110000000000000000000000000000000000000000000010000000
0000001000001000000000000000000000001000000000100001000000000000000000000000000000100000000000001000
0001000000000100100000000000000100100000000000000000000100000000000000000000000000000001000000000000
0000000000000001000000000000000000000000101000000000000000001001000001010000000100000100000000000000
0000000000000000000000000000000000001000000000000000000000000011000001000000000000000000101000000000
0100000000000000000000000000000000000000000000000000000010000000000000000000000000000000100001000000
1000000000001000000000000100000000000000100000000000000000100000000000000000010000000000000000000000
0000000000000000000001100000010000000000000000000000010000000010100000000000000000000000100010000000
0000100000000000000010000000000000000000000000000000001000100000000000000000000000000000001000000000
0000010000000000000010001000000000000000000000000000100000000010000000000000000000000000000000000000
0000000001000000000000000001000000100000000000000000000000000000000000010000001000000001000000000000
0000000000000000000000100010100000000000100010000000010000000000000000000000000000000000000000000000
0000000000000000000100000010000000000000010000000000000000000000000100000000000100000000000000000000
0000000000000000000000001100100000000001000000000000000010000000000000000000000000100010000000000001
0000000010000000000000010000000000000000000000000000001000001000000000000100000000010000000000001000
0000000000000000000000001010000000000000000000001000000000000000010000000000000000000000000000000000
0000000110000000000010000000000100000000000000000000000000000000000000000100000000000000001000000000
0100010000000000000000000000000000000000100000000000000000000000001000000000000000000000000000000101
0001100000000001000000000000010000100000000000000000000000000000001000100000000000011000000000000000
1000000000000000000000000000000000000001000000000000000100010101000100000000000000000000000000000000
0000000001000000000000000000000000001000000000000000000000000000010000000000000000000000100000000000
0000100000000001000000010000000100000000000000000000000000000000000000000000100000000000000000000000
0000000001001000000000000000000000001010000000000000000000000000000000000000001000000000000100000000
0000000000000010010000000000000001010100000000000000000000000000000000000000000000010000000000100000
0010000101000000000000000000000000001000000000000010000000001000000000000000000000000000000000000000
0000000000000000000000000000000000010000100000001000000000000000000000000000000000000100000000000000
0000000000000000000000000010000010000000000000000000000000000000000100000000000000000000000000000010
0000000000000000100100001000001000000010000000010000000000000000000000000000000000000000000000000000
0000000000000000000000000100000000000000000000000000000000000000000000000000000010001000000010000000
0000000000000000100000000000000000000000000100000000000000100000000000000011000000000000000000000000
0000000000000000000000000000000000000000001000000010000000000000000000000001000000000000000001000000
0010010000100000000000001000000000000000000001001000000010000000100000001000000000000000000000000000
0000000000000000000000000000000000000000000010000000000000000000001000000000001000000100000000010000
0000000000000110000000000000000000000000000000000000000000000000000000000000000000000000000000000100
0000000000000100000000000000000000000000100000000000000000000000000000000001000000000000000000010000
0000000000000000000000000000100000000010000010000100000001010000000100000000000001000000000000000000
0100000000100000000000000000000000000000000000001000000000000000000110000000000001010000000000000000
0000000000000000000000000000000000000100000100000000000000000000000000000000000000000000000101000010
0000000000001010000000000000000000000000000000000000100000000000001000000000000000000000000000000000
0000001000000000000000100000000000000000000000000001001000000000000010000000000000000000000000010000
0000000000000000000010001000000000000000000000000000000000000000001000000000001000000000010100000000
0000000000100000000001000001000000000000000000000000100001000000000100100000000000000000000000000000
0000000000000001000000000000000010000000000000000000000000000000000000000000001100010000000000000000
1000000010000000001000000010000000000000000010000000000001000000000001001000000000000000000100000000
0000000010000000000000000000000000000000000000001000001010001000001000000000000010000000000100000100
0100000000000000000101000000000000000000001000000000000000000000000000000000000000000000000000001100
0000000000000000000000000000000010000000000000001000000000000000000010000000000010000000000000000000
0000000000001000100000000001000000000100000000000000000001000100000000000011000000000000100000000000
0100100000000000000000000000000010000000000000000000000000001000000000000000000000000001010000000010
0000000000010000010010100000000000000000000000000000000000000000100000000000000000000000000000000000
0000100000000000110000000000000010000000000000000000000000000000100000000000000000000000000000000000
0100000000000000000010000000000000000000000010000000000000000011000000000000001000000000000000010000
0010000000000000000000000000100001000000000000000000000000000000000000000000001000001000001000000000
0000000000000000000000000000001100000000000001000001010001000000000000000000000000000000000000000000
0000000000000000000000000100000010000001000000001100001000000000000000000000000000000000000000000000
0010000000000000000000000000000000000000000000000100100000010000000000010100000000000000000000000000
0000000000000000110000000000000000000000000000000000000010000000000000100000000000000001000000000000
0000000100000000000000000000000100000000000000000000001000000000000001000000000000000000000000000000
0000100000001000100000010000000000000000000000000000000000000000000010000000000000000000000000000010
0000100000000000000000000000000000000000000010000000000010000000000000000000000000000010100000000000
0000000000000000000000000001010000000000000000000000000000000000000010000001000000000000000000001000
0000000000100000000000000000000000000000001000000000000000001000000000000000000000000000000000000100
0000000000000000000000000000000000000000001100010000000000001000000000000100001000000100100000100000
0000010001000000000000000000000000100000000000000000000000000000000000000000001000000000000000010001
1000000000000000000100000000000000000000000000000000000000000000000000000000000000001000000000001000
0000000000000000000000010000000000010000000001000000010100000000110000000001100000000001000000000000
0010000000000000100000000100000000000000000000000000000100000000000000000000000000000000000000000000
0000011000000000000000000000000000000000010000000000000001010000000000000000000000000000000000000000
0000000010000000000000000000000000000000000000001100000000000000000000000000000000000000000000010000
0000000000000010000000000010000000000000000000000000000000000000000000000000000000011000000000000100
0000001000000000000000000001000100001000000000000100000100000000000000000000000000100000000000000000
0000000000000000000000000000000100000000010000000000000000000000010000000000010000100100000000000000
1000000000000000100000000000000000000010000001000000000000000000000000000001000000001000010010000000
1000000000000000000000000010000000000000000000000000000000000000000000001000000000000000000000000000
1010000000000001000000010000000000000000000000000000000000000100000001000000001000000000000100000000
0000000001000000011010000000000001000000000000000000000000001000000000001001000000000000000000000000
0000000100000000000000000000000000000000000000000000010000000100000000000000000000000100000000000000
0000000000000000010001000000010000000000000000000000000000000000010000000000000000000000000000000000
0000000000000000000000000000000000010000000000000010010011000000000000000000000000000001000000000000
0000000010000100000010000000000000000000010000000000000000000000000000000000000000000100000000000000
0000000010000000001000000000000000000000000100000010000000000000000000000000000000000000000000000001
0000000000000000000000000000000000001000000000000000000000000000000000000001000000000000000000010000
0000000000000000000000000000000000000000000001010000100000000000100000000000100001000000000000100000
0000000000000010000000000001000000000000000000000000000000100000000000000100010000000000000000000100
0000000100010000000000000000001000000000000000100000000001100000000000000010000000100000000000001010
0000010000000000000000000000000000000001000000000010000000000100000000010000000000000000000000000100
0000000100100000000000000010001000000000000000000000000000000000000000000000100000000000000001000000