目录
NC15033 小G有一个大树
大意：
给出一个数，求平衡点。
平衡点的定义是，删掉这个点之后，剩下的最大子树节点数最小
思路：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n;
vector<int> mp[N];
int dp[N];
int pos = 0x3f3f3f3f, maxn = 0x3f3f3f3f;
void dfs(int now, int fa) {
dp[now] = 1;
int tmp = -0x3f3f3f3f;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dfs(ne, now);
dp[now] += dp[ne];
tmp = max(tmp, dp[ne]);
}
tmp = max(tmp, n - dp[now]);
if (tmp < maxn) {
pos = now, maxn = tmp;
} else if (tmp == maxn) {
if (pos > now) pos = now;
}
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
mp[x].push_back(y), mp[y].push_back(x);
}
dfs(1, 0);
cout << pos << ' ' << maxn << endl;
return 0;
}
NC22598 Rinne Loves Edges
大意：
给出n个点的树，以及一个 “重要点” S，现在要求选择性删除一些边，使得原图中所有除 S 之叶子节点都不能到达 S。
定义删除一条边的代价为这条边的边权，求最小代价
思路：
因为是删掉一个树，所以dp[i]代表删掉以i为根的子树中全部叶子节点的最小花费
那么只需要判断是将i的出边全部删掉，还是只删掉i的入边即可
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n, m, s;
vector<pair<int, int> > mp[N];
int dp[N];
void dfs(int now, int fa, int pre) {
dp[now] = 0;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i].first, w = mp[now][i].second;
if (ne == fa) continue;
dfs(ne, now, w);
dp[now] += dp[ne];
}
if (mp[now].size() == 1) dp[now] = pre;
else dp[now] = min(dp[now], pre);
}
int main() {
cin >> n >> m >> s;
for (int i = 0; i < m; i++) {
int x, y, w;
cin >> x >> y >> w;
mp[x].push_back({y, w});
mp[y].push_back({x, w});
}
for (int i = 0; i < mp[s].size(); i++) {
int ne = mp[s][i].first, w = mp[s][i].second;
dfs(ne, s, w);
dp[s] += dp[ne];
}
cout << dp[s] << endl;
return 0;
}
NC24953 Cell Phone Network
大意：
求点的最小点覆盖裸题
思路：
dp[i][0]:以i为根节点的子树，第i个结点的父结点被选的最小花费
dp[i][1]:以i为根节点的子树，第i个结点有一个子节点被选的最小花费
dp[i][2]:以i为根节点的子树，第i个节点本身被选的最小花费
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n, dp[N][3];
vector<int> mp[N];
void dfs(int now, int fa) {
dp[now][2] = 1;
int sum = 0;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dfs(ne, now);
dp[now][0] += min(dp[ne][1], dp[ne][2]); //当前点由父节点覆盖
dp[now][2] +=
min({dp[ne][0], dp[ne][1], dp[ne][2]}); //当前点由自身覆盖
sum += min(dp[ne][1] , dp[ne][2]);//子节点被覆盖的花费
}
dp[now][1] = 0x3f3f3f3f;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dp[now][1]=min(dp[now][1],sum - min(dp[ne][1], dp[ne][2]) + dp[ne][2]);
}
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
mp[x].push_back(y);
mp[y].push_back(x);
}
dfs(1, 0);
cout << min(dp[1][1], dp[1][2]);
return 0;
}
NC50505 二叉苹果树
大意： 有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的点。这棵树共 N 个节点，编号为 1 至 N，树根编号一定为 1。我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。这里的保留是指最终与1号点连通。1 ≤ Q < N ≤ 100.N≠1,
题解： 本题是分组背包的变形，本题问的是保留m条边可以得到的最大的苹果树，而分析树的性质我们可以知道，如果想要保留子树，那么子树的父节点必须保留，那么这题就变成了一道有依赖的背包问题，背包体积为要保留的树边+1(把边转化为点)，然后把每条边的权值转移到对应的子节点上去
#include <bits/stdc++.h>
using namespace std;
const int N = 1e2 + 5;
typedef long long LL;
int n, q, dp[N][N];
//dp[i][j]代表以i为根的子树保留j个节点的最大权值
vector<pair<int, int> > mp[N];
void dfs(int now, int fa, int pre) {
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i].first, w = mp[now][i].second;
if (ne == fa) continue;
dfs(ne, now, w);
for (int j = q - 1; j >= 0; j--) {//必须要选根节点，所以容量变为q-1
for (int k = 0; k <= j; k++) {
dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[ne][k]);
}
}
}
for (int i = q; i >= 1; i--) {
dp[now][i] = dp[now][i - 1] + pre; //选上这个根节点
}
dp[now][0] = 0;
}
int main() {
cin >> n >> q;
for (int i = 0; i < n - 1; i++) {
int x, y, w;
cin >> x >> y >> w;
mp[x].push_back({y, w});
}
q++;//q要+1，因为q个边要保留q+1个点
dfs(1, 0, 0);
cout << dp[1][q] << endl;
return 0;
}
NC51178 没有上司的舞会
最大点独立集裸题
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n, w[N],dp[N][2];
vector<int> mp[N];
void dfs(int now, int fa) {
dp[now][1] = w[now];
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dfs(ne, now);
dp[now][0] += max(dp[ne][0], dp[ne][1]);
dp[now][1] += dp[ne][0];
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n - 1; i++) {
int x, y;
cin >> x >> y;
mp[x].push_back(y), mp[y].push_back(x);
}
dfs(1, 0);
cout << max(dp[1][0], dp[1][1]);
return 0;
}
POJ1463 Strategic game
求边的最小点覆盖裸题，和点的最小点覆盖不同的是，这个题要求每个边至少选一个点
对于一个点来说，如果不选它，那么需要选全部的子节点，如果选他，那么子节点可选可不选
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n, dp[N][2];
vector<int> mp[N];
void dfs(int now, int fa) {
dp[now][1] = 1;
int sum = 0;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dfs(ne, now);
dp[now][1] += min(dp[ne][1], dp[ne][0]);
dp[now][0] += dp[ne][1];
}
}
int main() {
while (scanf("%d", &n) != EOF) {
memset(dp, 0, sizeof dp);
for (int i = 0; i < n; i++) mp[i].clear();
for (int i = 0; i < n; i++) {
int x, num;
scanf("%d:(%d)", &x, &num);
for (int j = 0; j < num; j++) {
int y;
scanf("%d", &y);
mp[x].push_back(y);
mp[y].push_back(x);
}
}
dfs(0, -1);
cout << min(dp[0][0], dp[0][1]) << endl;
}
return 0;
}
NC202475 树上子链
大意：
给定一棵树 T ，树 T 上每个点都有一个权值(有正有负)。
定义一颗树的子链的大小为：这个子链上所有结点的权值和 。
请在树 T 中找出一条最大的子链并输出。
思路：
如果想AC这道题的话，直接dp出每个点的最大次大子链，就行了，因为最后答案一定是某个点的最大次大之和
假如我们换一下题目，要求输出树上每个点包含这个点的最大链，这就必须换根了
换根写法：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n;
vector<int> mp[N];
LL dp[N][3], w[N],res[N];
void dfs1(int now, int fa) {
dp[now][0]=dp[now][1]=-0x3f3f3f3f3f3f3f3f;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dfs1(ne, now);
if(dp[now][0]<dp[ne][0]){
dp[now][1] = dp[now][0];
dp[now][0] = dp[ne][0];
}
else if(dp[now][1]<dp[ne][0]){
dp[now][1] = dp[ne][0];
}
}
dp[now][0] = max(0ll, dp[now][0]) + w[now];
dp[now][1] = max(0ll, dp[now][1]) + w[now];
}
void dfs2(int now, int fa) {
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
if(dp[ne][0]+w[now]==dp[now][0]){
dp[ne][2] =max({0ll,dp[now][1],dp[now][2]})+w[ne];
}
else {
dp[ne][2] =max({0ll,dp[now][0],dp[now][2]})+w[ne];
}
dfs2(ne, now);
}
res[now] = dp[now][0] + max(dp[now][2], dp[now][1])-w[now];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
mp[x].push_back(y), mp[y].push_back(x);
}
dfs1(1, 0);
dp[1][2] = w[1];
dfs2(1, 0);
LL ans =-0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= n; i++)ans= max(ans,res[i]);
cout << ans << endl;
return 0;
}
一次dp写法：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
typedef long long LL;
int n;
vector<int> mp[N];
LL dp[N][2], w[N],res[N];
void dfs1(int now, int fa) {
dp[now][0]=dp[now][1]=-0x3f3f3f3f3f3f3f3f;
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i];
if (ne == fa) continue;
dfs1(ne, now);
if(dp[now][0]<dp[ne][0]){
dp[now][1] = dp[now][0];
dp[now][0] = dp[ne][0];
}
else if(dp[now][1]<dp[ne][0]){
dp[now][1] = dp[ne][0];
}
}
dp[now][0] = max(0ll, dp[now][0]) + w[now];
dp[now][1] = max(0ll, dp[now][1]) + w[now];
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i];
}
for (int i = 0; i < n - 1; i++) {
int x, y;
cin >> x >> y;
mp[x].push_back(y), mp[y].push_back(x);
}
dfs1(1, 0);
LL ans =-0x3f3f3f3f3f3f3f3f;
for (int i = 1; i <= n; i++)ans= max(ans,dp[i][0]+dp[i][1]-w[i]);
cout << ans << endl;
return 0;
}
NC210473 吉吉王国
大意：
给出n和m，代表一个n个节点的树，现在要求删掉一些边，使得所有原来的叶子节点都和1号点不连通，且删掉边的总权值不超过m
问删掉的边中，最小的最大边是多少，如果不能符合要求，输出-1
思路：
最大最小值问题要想到二分求解，对于当前二分的mid，做dfs，计算dp[1]
dp[i]代表删掉所有i的子树，所需要的最小权值，转移方程：
if (w <= mid) dp[now] += min(w, dp[ne]);
else dp[now] += dp[ne];
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
typedef long long LL;
#define int LL
int n, q, dp[N],cnt=0,sum[N];
vector<pair<int, int> > mp[N];
void dfs(int now, int fa, int mid) {
for (int i = 0; i < mp[now].size(); i++) {
int ne = mp[now][i].first, w = mp[now][i].second;
if (ne == fa) continue;
dfs(ne, now, mid);
if (w <= mid) dp[now] += min(w, dp[ne]);
else dp[now] += dp[ne];
}
if(mp[now].size()==1&&now!=1){
dp[now] = 0x3f3f3f3f;
}
}
bool check(int mid) {
memset(dp, 0, sizeof dp);
dfs(1, 0, mid);
if (dp[1] <= q) return true;
else return false;
}
signed main() {
cin >> n >> q;
int l = 0x3f3f3f3f, r = 0,maxn;
for (int i = 0; i < n - 1; i++) {
int x, y, w;
cin >> x >> y >> w;
mp[x].push_back({y, w}),mp[y].push_back({x, w});
l = min(l, w), r = max(r, w);
}
maxn = ++r;
while (l < r) {
int mid = (l + r) >> 1; // 区别：有无加1
if (check(mid)) r = mid; //区别
else l = mid + 1; //区别
}
if (r == maxn) cout << -1 << endl;
else cout << l << endl;
return 0;
}