题目分析

题意：给一颗无根树，选择最少的节点将所有的边覆盖。

经典的树型DP,dp[i][0/1]表示选择或不选择i号节点的最优值。

当选择了i号节点，他的子节点可选可不选，选择最优的。

当不选择i号节点，他的子节点必须被选。

最优返回dp[1][0]和dp[1][1]的较小值。

code

#include<bits/stdc++.h>

using namespace std;

const int N = 1500;

int n;

int ecnt, adj[N + 5], go[N * 2 + 5], nxt[N * 2 + 5];

int dp[N + 5][2];

inline void addEdge(int u, int v){

	nxt[++ecnt] = adj[u], adj[u] = ecnt, go[ecnt] = v;

	nxt[++ecnt] = adj[v], adj[v] = ecnt, go[ecnt] = u;

}

inline void DP(int u, int f){

	if(u == 0) return;

	dp[u][0] = 0;

	dp[u][1] = 1;

	for(int e = adj[u]; e; e = nxt[e]){

		int v = go[e];

		if(v == f) continue;

		DP(v, u);

		dp[u][0] += dp[v][1];

		dp[u][1] += min(dp[v][0], dp[v][1]);

	}

}

int main(){

	ios::sync_with_stdio(false);

	cin.tie(NULL), cout.tie(NULL);

	cin >> n;

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

		int x, k, y;

		cin >> x >> k;

		x++;

		for(int j = 1; j <= k; j++){

			int p; cin >> p;

			p++;

			addEdge(x, p);

		}

	}

	DP(1, 0);

	cout << min(dp[1][0], dp[1][1]) << endl;

	return 0;

}

巴特西

战略游戏 - 树型DP

题目分析

code

最新文章

热门文章