2016年4月19日 星期二

找最大團大小 (暴搜)

注意:
使用了 __int128 , __builtin_ctzll(), __builtin_popcountll() 
__int128 是 128位元的整數
__builtin_ctzll() 吃一個long long大小的數x 回傳最小的i 滿足x的第i個bit為1
__builtin_popcountll() 吃一個long long大小的數x 回傳x有幾個bit為1

main() 裡面處理的是輸入和建邊 找最大團大小主要和 sol() 和 clique() 有關
v[x]的第i個bit 代表x和i是否有邊
我選擇把點 照度數由小到大排序(但不確定這樣是否較好)

最主要的剪枝是 C[i]的使用 if( C[i]+sz <= ans ) return false;
C[i] 存的是 點i~N 所能構成的最大團大小
可以這樣剪是接下來的點 都會從i以後選 那最多就也只能選C[i]個的緣故

另一個剪枝是 if( U_size+sz <= ans ) return false;
就是剩餘的候選人 都選還是不能比當前答案更優就返回
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;

int N;

int num[100], per[100], c[100], cnt[100];
__int128 v[100], one = 1;

inline bool test(int x, int y)
{
    int d = 0;

    while( x || y )
    {
        if( x%2 != y%2 ) d++;
        x/=2, y/=2;
    }

    return d > 4;
}

inline int size(__int128 x)
{
    ll l = x>>40, r = x&((one<<40)-1);
    return __builtin_popcountll(l)+__builtin_popcountll(r);
}

inline bool cmp(int a, int b)
{
    return cnt[a] < cnt[b];
}

int ans;

bool clique(__int128 U, int sz)
{
    if( U == 0 )
    {
        if( sz > ans )
        {
            ans = sz;
            return true;
        }
        return false;
    }

    while( U )
    {
        ll l = U>>40, r = U&((1LL<<40)-1);
        int U_size = size(U);

        if( U_size+sz <= ans ) return false;

        int i;
        if( r ) i = __builtin_ctzll(r);
        else i = 40+__builtin_ctzll(l);

        if( c[i]+sz <= ans ) return false;

        U -= one<<i;
        if( clique(U&v[i], sz+1) ) return true;
    }

    return false;
}

void sol()
{
    ans = 0;
    __int128 S = 0;

    for(int Ni = N-1; Ni >= 0; Ni--)
    {
        S |= (one<<Ni);
        clique(S&v[Ni], 1);
        c[Ni] = ans;
    }

    return;
}

int main()
{
    int T;
    scanf("%d", &T);

    while( T-- )
    {
        scanf("%d", &N);

        for(int Ni = 0; Ni < N; Ni++)
        {
            scanf("%d", &num[Ni]);

            per[Ni] = Ni;
            c[Ni] = cnt[Ni] = 0;
            v[Ni] = 0;
        }

        for(int Ni = 0; Ni < N; Ni++)
            for(int Nj = 0; Nj < N; Nj++)
                if( test(num[Ni], num[Nj]) )
                    cnt[Ni]++;

        sort(per, per+N, cmp);

        for(int Ni = 0; Ni < N; Ni++)
            for(int Nj = 0; Nj < N; Nj++)
                if( test(num[per[Ni] ], num[per[Nj] ]) )
                    v[Ni] += one<<Nj;

        sol();

        printf("%d\n", ans);
    }
}

沒有留言:

張貼留言