题解 P3475 【[POI2008]POD-Subdivision of Kingdom】

hongzy · 2018-06-22 19:14:14 · 题解

对于这题，首先，预处理出每个二进制数中1的个数.但是2^{26}的时间复杂度稍高，可以只处理到2^{13}，每次求的时候分成前13位和后13位分别处理.

dfs时，首先让集合S1为空，集合S2为所有点。从S2里选\frac{n}{2}个点加到S1里.每次选一个点i加入S1时，减去原S1与i连的边数，加上i与新S2连的边数.

上述过程均使用位运算实现，二进制存储一个点的相连的点，使用按位与(&)运算，配合上述求二进制1个数的方法，就可以计算贡献.

#include <iostream>
#include <cstdio>
using namespace std;

const int N = 27;

int n, m, ans(N * N), s;
int e[N], cnt1[(1 << (N / 2)) + 10];

int Count1(int x) {
    return cnt1[x >> (N/2)] + cnt1[x - ((x >> N/2) << N/2)];
}

void dfs(int pos, int k, int sum, int s1, int s2) {
    if(k == n / 2) {
        if(sum < ans) s = s1, ans = sum;
        return ;
    }
    for(int i=pos+1, ns2; i<=n; i++) {
        ns2 = s2 ^ (1 << i-1);
        dfs(i, k+1, sum - Count1(e[i] & s1) + Count1(e[i] & ns2), s1 | (1 << i-1), ns2);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for(int i=0; i<1<<(N/2); i++)
        cnt1[i] = cnt1[i>>1] + (i & 1);
    for(int i=1, u, v; i<=m; i++) {
        scanf("%d%d", &u, &v);
        e[u] |= (1 << v-1);
        e[v] |= (1 << u-1);
    }
    dfs(0, 0, 0, 0, (1<<n)-1);

    for(int i=1; i<=n; i++)
        if(s >> i-1 & 1) printf("%d ", i);
    printf("\n");
    return 0;
}