组队（最大团）
【问题描述】小秋秋想出去玩了。。小秋秋有许多朋友，有一些小秋秋的朋友相互之间也是朋友。。。小秋秋觉得自己带不是朋友的两个朋友出去玩会出现尴尬。。。（好纠结）小秋秋想知道自己最多可以带多少朋友出去玩以及带人最多的方案数。。【输入文件】(input.txt)第一行两个数，n,m分别表示小秋秋的朋友数，以及他们之间相互认识的关系对数。接下来m行，每行两个整数x,y表示朋友x和朋友y他们相互认识。【输出文件】(output.txt)一行两个整数，分别表示能选出一起出去玩的最大人数，以及能达到最大人数的方案数。【样例输入】4 51 22 33 11 42 4【样例输出】3 2【数据约定】test 0 1 2 3 4 5 6 7 8 9n 5 10 15 20 25 30 35 40 45 50考场上随便乱状压了一下，没有考虑 n > 20 的情况，搞了三十分。
正解是什么呢？。。搜索。不过可以有很多很好的办法可以降低所耗时间：
1.位运算压缩邻接矩阵。每次判断只需要 O(1) 的时间。
2.最优化剪枝。如果当前所搜到的点所在团的最大值加上当前的答案比最大答案要小，那么肯定可以剪枝，因为不可能更优了。
Code :
#include
#include
#include
#include #define swap(a, b, t) ({t _ = (a); (a) = (b); (b) = _;})
#define max(a, b) ({int _ = (a), __ = (b); _ > __ ? _ : __;})
#define min(a, b) ({int _ = (a), __ = (b); _ < __ ? _ : __;})#define maxn 55#define fill(a, i) ((a) | (1LL << (i) - 1))
#define full(a, i) (((a) >> (i) - 1) & 1LL)int n, m, ans1, ans2;
long long e[maxn];
int maxi[maxn];void renew(int x)
{if (x == ans1) ++ ans2;else if (x > ans1) ans1 = x, ans2 = 1;
}void dfs(int u, int sum, long long now)
{if (u == n + 1) return renew(sum);if ((now & e[u + 1]) == now && sum + maxi[u + 1] >= ans1)dfs(u + 1, sum + 1, fill(now, u + 1));dfs(u + 1, sum, now);
}int main()
{freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);scanf("%d%d", & n, & m);for (int u, v; m --; ){scanf("%d%d", & u, & v);e[u] = fill(e[u], v), e[v] = fill(e[v], u);}for (int i = 1; i <= n; ++ i) e[i] = fill(e[i], i);for (int i = n; i >= 1; -- i)dfs(i, 1, fill(0, i)), maxi[i] = ans1;printf("%d %d\n", ans1, ans2);return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！