Codeforces 599E Sandy and Nuts 状压DP

链接

Codeforces 599E Sandy and Nuts

题意

一棵树，给你若干边和若干点的最近公共祖先，求合法的树有多少个

思路

看题后没什么思路的动归。 用 dp[root][mask] 表示 root为根，选择 mask 的二进制中那些点的子树的状态。所以转移方程就是 dp[root][mask] += dp[subRoot][subMask] * dp[root][subMask ^ mask]。其中的subRoot表示mask的一颗子树的根，subMask是这颗子树中的点， subMask ^ mask 就是 mask 中出去 subMask 这个子树的其余点。最后的答案就是 dp[0]](1 << n) - 1。细节见代码注释。

代码

#include 
#include 
#include 
#include 
#include 
#include #define INF 99999999
#define LL long long
#define MAXN 100005
using namespace std;
int n, m, p;
bool vis[15][15];
LL dp[15][1 << 15];
int a[105], b[105], c[105];
bool isInside(int x, int mask){return (mask >> x) & 1;
}LL work(int root, int mask){if (dp[root][mask] != -1){return dp[root][mask];}//去除根节点int sub = mask - (1 << root);int x = 0;//保证子树中有点while (true){if (isInside(x, sub)) break;++x;if (x >= n) break;}LL ans = 0;//在sub枚举子树for (int subMask = sub; subMask; subMask = (subMask - 1) & sub){if (!isInside(x, subMask)) continue;bool flag = false;for (int i = 0; i < n; ++i){if (i == root) continue;for (int j = 0; j < n; ++j){if (j == root) continue;//i与j有边相连却不在同一颗子树中if (vis[i][j] && (isInside(i, subMask) ^ isInside(j, subMask))){flag = true;break;}}if (flag) break;}if (flag) continue;int cnt = 0, son;for (int i = 0; i < n; ++i){//root与该子树存在多条边相连if (vis[root][i] && isInside(i, subMask)){++cnt;son = i;}}if (cnt > 1) continue;for (int i = 1; i <= p; ++i){//LCA是根，但两个后代都在子树中if (c[i] == root && isInside(a[i], subMask) && isInside(b[i], subMask)){flag = true;break;}//LCA在子树中，但有后代不在子树中if (isInside(c[i], subMask) && !(isInside(a[i], subMask) && isInside(b[i], subMask))){flag = true;break;}}if (flag) continue;if (cnt != 1){for (int i = 0; i < n; ++i){if (!isInside(i, subMask)) continue;ans += work(i, subMask) * work(root, mask ^ subMask);}}else{ans += work(son, subMask) * work(root, mask ^ subMask);}}return dp[root][mask] = ans;
}int main(){
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE//dp[root][mask] += dp[subRoot][subMask] * dp[root][mask ^ subMask];int x, y;scanf("%d%d%d", &n, &m, &p);for (int i = 1; i <= m; ++i){scanf("%d%d", &x, &y);vis[x - 1][y - 1] = true;vis[y - 1][x - 1] = true;}for (int i = 1; i <= p; ++i){scanf("%d%d%d", &a[i], &b[i], &c[i]);--a[i], --b[i], --c[i];}memset(dp, -1, sizeof(dp));for (int i = 0; i < n; ++i){dp[i][1 << i] = 1;}LL ans = work(0, (1 << n) - 1);printf("%I64d\n", ans);
}

查看原文：http://www.macinchang.com/2016/03/12/562/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！