Codeforces Gym100502G：Outing（缩点+有依赖的树形背包）

http://codeforces.com/gym/100502/attachments

题意：有n个点，容量为tol，接下来n个关系，表示选了第i个点，那么第xi个点就必须被选。问最多可以选多少个点使得不超过容量tol。

思路：由题目样例可得，边可能出现自环的情况，这个时候这条边其实没用。然后因为是一个图，所以需要缩点，缩完之后用一个sz数组表示点的大小，重新建一幅图。因为有可能是森林，所以需要添加一个虚根，使得其变成一棵树。然后题目就转变为求有依赖的树上背包了。

我是学了这篇博客的写法：http://blog.csdn.net/y990041769/article/details/38068223

dp[i][j]表示以i为根的子树在容量为j的时候能放的点的最大个数。sz[i]表示i结点的大小。

因为i是必须选的（不然其儿子都没办法选），那么一开始就直接赋予其值。

         for(int j = tol; j >= sz[u]; j--) { // 枚举容量

             for(int k = ; k <= j - sz[u]; k++) { // k表示能分配给子节点的容量

                 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);

             }

         }

接下来第一层循环是像01背包一样，枚举能够放下u（根结点）自己的容量，第二层循环k代表能够分配给儿子的容量，因为根结点自己已经放进去了，所以是j-sz[u]。就这样可以更新完u这个根节点了。

 #include <bits/stdc++.h>

 using namespace std;

 #define N 1010

 struct Edge {

     int v, nxt;

 } edge[N*], e[N*];

 int n, tol, head[N], tot, h[N], t, dfn[N], low[N], belong[N], vis[N], num, tid, sz[N], deg[N], dp[N][N];

 stack<int> sta;

 void Add(int u, int v) { edge[tot] = (Edge) {v, head[u]}; head[u] = tot++; }

 void add(int u, int v) { e[t] = (Edge) {v, h[u]}; h[u] = t++; }

 void tarjan(int u) {

     sta.push(u);

     vis[u] = ;

     dfn[u] = low[u] = ++tid;

     for(int i = head[u]; ~i; i = edge[i].nxt) {

         int v = edge[i].v;

         if(!dfn[v]) {

             tarjan(v);

             low[u] = min(low[u], low[v]);

         } else if(vis[v]) {

             low[u] = min(low[u], dfn[v]);

         }

     }

     if(low[u] == dfn[u]) {

         num++;

         int top = -;

         while(top != u) {

             top = sta.top(); sta.pop();

             belong[top] = num;

             sz[num]++;

             vis[top] = ;

         }

     }

 }

 void BuildGraph() {

     memset(head, -, sizeof(head));

     memset(h, -, sizeof(h));

     t = tot = ;

     for(int i = ; i <= n; i++) {

         int j; scanf("%d", &j);

         if(i == j) continue;

         Add(j, i);

     }

     for(int i = ; i <= n; i++)

         if(!dfn[i]) tarjan(i);

     // 将环缩点重新建图

     for(int u = ; u <= n; u++) {

         for(int i = head[u]; ~i; i = edge[i].nxt) {

             int v = edge[i].v;

             if(belong[u] != belong[v]) {

                 add(belong[u], belong[v]);

                 deg[belong[v]]++;

             }

         }

     }

     for(int i = ; i <= num; i++) // 设一个虚根将森林变成树

         if(!deg[i]) add(, i);

 }

 void dfs(int u) {

     for(int i = tol; i >= sz[u]; i--) dp[u][i] = sz[u]; // 初始状态必须有这个结点的sz

     for(int i = h[u]; ~i; i = e[i].nxt) {

         int v = e[i].v;

         dfs(v);

         for(int j = tol; j >= sz[u]; j--) { // 枚举容量

             for(int k = ; k <= j - sz[u]; k++) { // k表示能分配给子节点的容量

                 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]);

             }

         }

     }

 }

 void Bag() {

     dfs();

     printf("%d\n", dp[][tol]);

 }

 int main() {

     scanf("%d%d", &n, &tol);

     BuildGraph();

     Bag();

     return ;

 }

巴特西

Codeforces Gym100502G：Outing（缩点+有依赖的树形背包）

最新文章

热门文章