首页 algorithm 杂杂的算法知识

# 树的直径

1072. 树的最长路径 - AcWing 题库

对于每个点，找到最大的儿子和次大的儿子，计算二者的距离和

找到最大的距离和，就是直径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10010, M = 2 * N;
int head[M], ne[M], to[M], w[M], idx;
int d1[N], d2[N], res;
int n;
void add(int x, int y, int z)
{
	ne[idx] = head[x], w[idx] = z, to[idx] = y, head[x] = idx++;
}
void dfs(int u, int fa)
{
	for(int i = head[u]; ~i; i = ne[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u);

		if(d1[v] + w[i] >= d1[u]) d2[u] = d1[u], d1[u] = d1[v] + w[i];
		else if(d1[v] + w[i] >= d2[u]) d2[u] = d1[v] + w[i];
	}
	res = max(res, d1[u] + d2[u]);
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
    	int a, b, c;
    	cin >> a >> b >> c;
    	add(a, b, c);
    	add(b, a, c);
    }
    dfs(1, 0);
    cout << res;
	return 0;
}

1073. 树的中心 - AcWing 题库

希望最远距离最近

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 10010, M = N * 2, inf = 1e18;
int head[M], ne[M], to[M], w[M], idx;
int s1[N], s2[N], d1[N], d2[N], up[N];
//s1 记录最大的子节点 s2 记录次大的子节点
//d1 记录最长的长度 d2 记录次长的长度
int n;

void add(int x, int y, int z)
{
	to[idx] = y, ne[idx] = head[x], w[idx] = z, head[x] = idx++;
}
void dfs1(int u, int fa)
{
	for(int i = head[u]; ~i; i = ne[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs1(v, u);

		if(d1[v] + w[i] >= d1[u])
		{
			d2[u] = d1[u], d1[u] = d1[v] + w[i];
			s2[u] = s1[u], s1[u] = v; 
		}
		else if(d1[v] + w[i] > d2[u])
		{
			d2[u] = d1[v] + w[i], s2[u] = v;
		}
	}
}
void dfs2(int u, int fa)
{
	for(int i = head[u]; ~i; i = ne[i])
	{
		int v = to[i];
		if(v == fa) continue;
		if(s1[u] == v) up[v] = w[i] + max(d2[u], up[u]);
		else up[v] = w[i] + max(d1[u], up[u]);
		dfs2(v, u);
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
    	int a, b, c;
    	cin >> a >> b >> c;
    	add(a, b, c); add(b, a, c);
    }

    //遍历找到每个节点的儿子对这个节点的贡献
    dfs1(1, 0);
    //遍历找到每个节点的父节点对这个节点的贡献
    dfs2(1, 0);

    int res = inf;
    for(int i = 1; i <= n; i++)
    	res = min(res, max(d1[i], up[i]));
    cout << res;
	return 0;
}

# 树的最大独立集

每个节点有选和不选两个决策： dp[i][0/1]

P1352 没有上司的舞会 - 洛谷

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 6e3 + 10;
int n, r[N];
vector<int> e[N];
int f[N], g[N];
//f[i] 表示 选i的最大快乐值
//g[i] 表示 不选i的最大快乐值 
bool badr[N];
void dfs(int u)
{
	f[u] = r[u];
	for(auto v: e[u])
	{
		dfs(v);
		
		f[u] += g[v];
		g[u] += max(g[v], f[v]); 
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> r[i];
	for(int i = 1; i < n; i++)
	{
		int l, k;
		cin >> l >> k;
		e[k].push_back(l);
		badr[l] = true;
	}
	int root;
	for(int i = 1; i <= n; i++)
	{
		if(!badr[i]) root = i;
	}
	dfs(root);
	cout << max(f[root], g[root]);
	return 0;
}

# 树的最小点覆盖

点覆盖边

只需要考虑两种情况

  • 使用节点 ii
  • 不使用节点 ii ，节点 ii 被其子节点覆盖

323. 战略游戏 - AcWing 题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<bits/stdc++.h>
using namespace std;
const int N = 1510;
vector<int> e[N];
int f[N][2], st[N];
//f[u][0] 表示不选u 被子节点覆盖
//f[u][1] 表示选u 
void dfs(int u, int fa)
{
	f[u][1] = 1, f[u][0] = 0;
	for(auto v: e[u])
	{
		if(v == fa) continue;
		dfs(v, u);

		f[u][0] += f[v][1];
		f[u][1] += min(f[v][0], f[v][1]);
	}
}
signed main()
{
	int n, u, v, m;
    while(~scanf("%d", &n))
    {
    	for(int i = 0; i < n; i++)
    	{
    		scanf("%d:(%d)", &u, &m);
    		while(m--)
    		{
    			scanf("%d", &v);
    			e[u].push_back(v);
    			e[v].push_back(u);
    		}
    	}
    	dfs(0, -1);
    	printf("%d\n", min(f[0][1], f[0][0]));
    	for(int i = 0; i < n; i++) e[i].clear();
    }
	return 0;
}

# 树的最小支配集

点覆盖点

要考虑三种情况

  • 使用节点 ii
  • 不使用节点 ii ，节点 ii 被其子节点覆盖
  • 不使用节点 ii ，节点 ii 被其父节点覆盖

1077. 皇宫看守 - AcWing 题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1510;
vector<int> e[N];
int w[N], f[N][3];
//f[i][0] 在i点放士兵
//f[i][1] 不在i点放士兵，由儿子覆盖
//f[i][2] 不在i点放士兵，由父节点覆盖
int n;
void dfs(int u, int fa)
{
	f[u][0] = w[u];
	int flag = 1, tmp = 1e18; 
	for(auto v: e[u])
	{
		if(v == fa) continue;
		dfs(v, u);

		f[u][0] += min({f[v][0], f[v][1], f[v][2]});
		f[u][2] += min(f[v][0], f[v][1]);

		if(f[v][0] <= f[v][1])
		{
			flag = 0;
			f[u][1] += f[v][0]; 
		}
		else
		{
			f[u][1] += f[v][1];
			tmp = min(tmp, f[v][0] - f[v][1]);
		}
	}
	if(flag) f[u][1] += tmp;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
    	int u, m;
    	cin >> u >> w[u] >> m;
    	while(m--)
    	{
    		int v; cin >> v;
    		e[u].push_back(v);
    		e[v].push_back(u);
    	}
    }
    dfs(1, 0);
    cout << min(f[1][0], f[1][1]);
	return 0;
}

# 树上背包

1074. 二叉苹果树 - AcWing 题库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 105, M = 2 * N;
int n, q;
int head[M], ne[M], to[M], w[M], idx;
int f[N][N], sz[N];//在节点i保留j根树枝的最大苹果数

void add(int x, int y, int z)
{
	ne[idx] = head[x], to[idx] = y, w[idx] = z, head[x] = idx++;
}
void dfs(int u, int fa)
{
	for(int i = head[u]; ~i; i = ne[i])
	{
		int v = to[i];
		if(v == fa) continue;
		dfs(v, u);
		sz[u] += sz[v] + 1;
		for(int j = min(sz[u], q); j; j--)
		{
			for(int x = 0; x <= j - 1; x++)
			{
				f[u][j] = max(f[u][j], f[v][x] + f[u][j - x - 1] + w[i]);
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    memset(head, -1, sizeof head);
	cin >> n >> q;
	for(int i = 1; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	dfs(1, 0);
	cout << f[1][q];
	return 0;
}