題目大意：
有一群學(xué)生，其中有些人是相互認(rèn)識(shí)的。將學(xué)生分為兩組，這兩組的人數(shù)最大只能相差1。
定義一個(gè)學(xué)生的“孤獨(dú)指數(shù)”為組內(nèi)他不認(rèn)識(shí)的人的人數(shù)。
問怎么分組，才能使這兩組中最孤獨(dú)學(xué)生的“孤獨(dú)指數(shù)”最小。
思路：
想不到算法，于是看Discuss。原來是用枚舉。。
暴力枚舉每一種分組情況，求該情況下“最孤獨(dú)學(xué)生的孤獨(dú)指數(shù)”。
據(jù)說數(shù)據(jù)很弱，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;
}