本文主要是介绍uva 649 - You Who?(暴力+位运算），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：uva 649 - You Who?
题目大意：给出n个人，每个人有自己认识的一些人，现在要将这些人分成两堆，两堆人的人数差不能大于1。每个时刻，一个人可以认识另一个人，但是不是相互的，即可能a用第一个时刻去认识b，而b可能用第一个时刻去认识c。你的任务是要分配所有人，要求两堆人中互相认识，并且耗时最小。
解题思路：因为n最大只有24，所以dfs，剪枝，当某一堆的人数大于一半的时候即为不可（因为两堆人数之差不能大于1），然后枚举出情况后进行判断，维护最小值。
#include <stdio.h>
#include <string.h>#define max(a,b) (a)>(b)?(a):(b)
#define cal(a,b) (a&(1<<b))const int N = 30;
const int INF = 0x3f3f3f3f;int ans, recAns, n, m, k[N], cnt;inline void init () {cnt = 0;m = (n+1)/2;ans = INF;memset(k, 0, sizeof(k));int u, a, t;for (int i = 0; i < n; i++) {scanf("%d%d", &u, &t);u--;k[u] |= (1<<u);for (int j = 0; j < t; j++) {scanf("%d", &a);k[u] |= (1<<(a-1));}}
}inline int bitcount (int x) {return x == 0 ? 0 : (bitcount(x/2) + (x&1));
}inline int solve (int s) {int val = 0, t;int c = bitcount(s);int ss = ((1<<n) - 1) ^ s;for (int i = 0; i < n; i++) {if (cal(s, i)) {t = bitcount(s&k[i]);val = max(val, c - t);} if (cal(ss, i)) {t = bitcount(ss&k[i]);val = max(val, n - c - t);}if (val > ans) return ans;}return val;
}inline void dfs (int d, int s) {if (cnt > m || d - cnt > m) return;if (d == n) {int cost = solve (s);if (cost < ans) {ans = cost;recAns = s;}return;}dfs (d + 1, s);cnt++;dfs (d + 1, s | (1<<d));cnt--;
}inline void put () {printf("%d\n", ans);int a = 0, b = 0, A[N], B[N];for (int i = 0; i < n; i++) {(recAns & (1<<i)) == 0 ? A[a++] = i + 1 : B[b++] = i + 1;}printf("%d", a);for (int i = 0; i < a; i++)printf(" %d", A[i]);printf("\n");printf("%d", b);for (int i = 0; i < b; i++)printf(" %d", B[i]);printf("\n");
}int main () {int cas = 0;while (scanf("%d", &n) == 1) {if (cas++) printf("\n");init ();dfs (0, 0);put ();}return 0;
}这篇关于uva 649 - You Who?(暴力+位运算）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
