嘟嘟嘟
这好像是一种树上背包.
我们令 dp[i][j] 表示在 i 所在的子树中 (包括节点 i) 分离出一个大小为 j 的子树最少需割多少条边.
那么转移方程就是
dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k] - 1) (v 是 u 的一个儿子)
理解起来就是在 u 所在子树中切 j 个节点, 等于在 u 中切 j - k 个节点加上在 v 所在子树中切 k 个节点所需要切的边数之和. 又因为切出来的这两部分要合并得到一个节点数为 j 的, 所以要减 1.
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<algorithm>
- #include<cstring>
- #include<cstdlib>
- #include<cctype>
- #include<vector>
- #include<stack>
- #include<queue>
- using namespace std;
- #define enter puts("")
- #define space putchar(' ')
- #define Mem(a, x) memset(a, x, sizeof(a))
- #define rg register
- typedef long long ll;
- typedef double db;
- const int INF = 0x3f3f3f3f;
- const db eps = 1e-8;
- const int maxn = 155;
- inline ll read()
- {
- ll ans = 0;
- char ch = getchar(), last = ' ';
- while(!isdigit(ch)) {last = ch; ch = getchar();}
- while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();}
- if(last == '-') ans = -ans;
- return ans;
- }
- inline void write(ll x)
- {
- if(x <0) x = -x, putchar('-');
- if(x>= 10) write(x / 10);
- putchar(x % 10 + '0');
- }
- int n, p;
- vector<int> v[maxn];
- int du[maxn], siz[maxn];
- int dp[maxn][maxn];
- void dfs(int now)
- {
- siz[now] = 1;
- for(int i = 0; i <(int)v[now].size(); ++i)
- {
- dfs(v[now][i]);
- siz[now] += siz[v[now][i]];
- for(int j = siz[now]; j>= 0; --j)
- for(int k = 1; k < j; ++k)
- dp[now][j] = min(dp[now][j], dp[now][j - k] + dp[v[now][i]][k] - 1);
- }
- }
- int main()
- {
- n = read(); p = read();
- for(int i = 1; i < n; ++i)
- {
- int x = read(), y = read();
- v[x].push_back(y);
- du[x]++;
- }
- for(int i = 0; i <= n; ++i)
- for(int j = 0; j <= n; ++j) dp[i][j] = INF;
- for(int i = 1; i <= n; ++i) dp[i][1] = du[i];
- dfs(1);
- int ans = dp[1][p]; // 本来就是根节点
- for(int i = 2; i <= n; ++i) ans = min(ans, dp[i][p] + 1); // 还要切除和父亲连的一条边
- write(ans); enter;
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2766436.html