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是必须选的（不然其儿子都没办法选），那么一开始就直接赋予其值。
1 for(int j = tol; j >= sz[u]; j--) { // 枚举容量 2 for(int k = 0; k <= j - sz[u]; k++) { // k表示能分配给子节点的容量 3 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]); 4 } 5 }
接下来第一层循环是像01背包一样，枚举能够放下u（根结点）自己的容量，第二层循环k代表能够分配给儿子的容量，因为根结点自己已经放进去了，所以是j-sz[u]。就这样可以更新完u这个根节点了。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 1010 4 struct Edge { 5 int v, nxt; 6 } edge[N*2], e[N*2]; 7 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]; 8 stack<int> sta; 9 10 void Add(int u, int v) { edge[tot] = (Edge) {v, head[u]}; head[u] = tot++; } 11 void add(int u, int v) { e[t] = (Edge) {v, h[u]}; h[u] = t++; } 12 13 void tarjan(int u) { 14 sta.push(u); 15 vis[u] = 1; 16 dfn[u] = low[u] = ++tid; 17 for(int i = head[u]; ~i; i = edge[i].nxt) { 18 int v = edge[i].v; 19 if(!dfn[v]) { 20 tarjan(v); 21 low[u] = min(low[u], low[v]); 22 } else if(vis[v]) { 23 low[u] = min(low[u], dfn[v]); 24 } 25 } 26 if(low[u] == dfn[u]) { 27 num++; 28 int top = -1; 29 while(top != u) { 30 top = sta.top(); sta.pop(); 31 belong[top] = num; 32 sz[num]++; 33 vis[top] = 0; 34 } 35 } 36 } 37 38 void BuildGraph() { 39 memset(head, -1, sizeof(head)); 40 memset(h, -1, sizeof(h)); 41 t = tot = 0; 42 for(int i = 1; i <= n; i++) { 43 int j; scanf("%d", &j); 44 if(i == j) continue; 45 Add(j, i); 46 } 47 for(int i = 1; i <= n; i++) 48 if(!dfn[i]) tarjan(i); 49 50 // 将环缩点重新建图 51 for(int u = 1; u <= n; u++) { 52 for(int i = head[u]; ~i; i = edge[i].nxt) { 53 int v = edge[i].v; 54 if(belong[u] != belong[v]) { 55 add(belong[u], belong[v]); 56 deg[belong[v]]++; 57 } 58 } 59 } 60 for(int i = 1; i <= num; i++) // 设一个虚根将森林变成树 61 if(!deg[i]) add(0, i); 62 } 63 64 void dfs(int u) { 65 for(int i = tol; i >= sz[u]; i--) dp[u][i] = sz[u]; // 初始状态必须有这个结点的sz 66 for(int i = h[u]; ~i; i = e[i].nxt) { 67 int v = e[i].v; 68 dfs(v); 69 for(int j = tol; j >= sz[u]; j--) { // 枚举容量 70 for(int k = 0; k <= j - sz[u]; k++) { // k表示能分配给子节点的容量 71 dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]); 72 } 73 } 74 } 75 } 76 77 void Bag() { 78 dfs(0); 79 printf("%d ", dp[0][tol]); 80 } 81 82 int main() { 83 scanf("%d%d", &n, &tol); 84 BuildGraph(); 85 Bag(); 86 return 0; 87 }