自动搬运

查看原文

来自洛谷，原作者为

	hongzy **

搬运于2025-08-24 21:49:22，当前版本为作者最后更新于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;
}