题目大意：
有一群学生，其中有些人是相互认识的。将学生分为两组，这两组的人数最大只能相差1。
定义一个学生的“孤独指数”为组内他不认识的人的人数。
问怎么分组，才能使这两组中最孤独学生的“孤独指数”最小。
思路：
想不到算法，于是看Discuss。原来是用枚举。。
暴力枚举每一种分组情况，求该情况下“最孤独学生的孤独指数”。
据说数据很弱，N最大才是4，囧。所以0msAC。
#include <stdio.h>
unsigned __int64 map[64];
int N;
int bit_cnt[256];
__inline int calc_cnt(unsigned __int64 val)
{
return bit_cnt[((char *)&val)[0]] +
bit_cnt[((char *)&val)[1]] +
bit_cnt[((char *)&val)[2]] +
bit_cnt[((char *)&val)[3]] +
bit_cnt[((char *)&val)[4]] +
bit_cnt[((char *)&val)[5]] +
bit_cnt[((char *)&val)[6]] +
bit_cnt[((char *)&val)[7]];
}
__inline int min(int a, int b)
{
return a < b ? a : b;
}
__inline int max(int a, int b)
{
return a < b ? b : a;
}
int main()
{
int i, j, k, l, r, arr[64], min_val;
unsigned __int64 mask;
freopen("e:\\test\\in.txt", "r", stdin);
for (i = 0; i < 256; i++) {
k = 0;
for (j = i; j; j &= j - 1)
k++;
bit_cnt[i] = k;
}
while (scanf("%d%d", &j, &k) != EOF) {
while (k--) {
scanf("%d", &i);
map[j] |= (unsigned __int64)1 << i;
}
if (j > N)
N = j;
}
for (i = 1; i <= N; i++)
map[i] |= (unsigned __int64)1 << i;
min_val = N;
for (i = 1; i <= N/2; i++)
arr[i] = i;
while (1) {
mask = 0;
for (i = 1; i <= N/2; i++)
mask |= (unsigned __int64)1 << arr[i];
l = r = N;
for (i = 1; i <= N; i++) {
if (mask & ((unsigned __int64)1 << i))
l = min(calc_cnt(map[i] & mask), l);
else
r = min(calc_cnt(map[i] & ~mask), r);
}
i = max(N/2 - l, N - N/2 - r);
if (i < min_val)
min_val = i;
for (i = N/2; i >= 1 && arr[i] == N + i - N/2; i--);
if (!i)
break;
arr[i]++;
for (j = 1; j + i <= N/2; j++)
arr[j + i] = arr[i] + j;
}
printf("%d\n", min_val);
return 0;
}