P2458 保安站岗

思路：
树形DP
三个状态：

• dp[i][0]：节点 i 位置放保安的最小花费
• dp[i][1]：节点 i 位置不放保安，但被子节点的保安看守
• dp[i][2]：节点 i 位置不放保安，但被父节点的保安看守

状态转移：

• dp[i][0]：节点 i 位置放保安，那么它可以合并子节点任何状态的最小值；
• dp[i][1]：节点 i 位置不放保安，但被子节点的保安看守，那么它可以合并一个子节点的状态 0 和其余子节点的状态 1 和状态 0 的小值；
• dp[i][2]：节点 i 位置不放保安，但被父节点的保安看守，那么它可以合并子节点除了状态 2 以外的状态。

最终答案：
min(dp[root][0],dp[root][1])
root设置为没有父节点的节点

下为代码：

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*

*/
const int maxm=15e2+5,inf=0x3f3f3f3f,mod=998244353;
int n, k[maxm], m;
vector<int> e[maxm];
vector<vector<int>> dp(maxm, vector<int>(3,0));

void dfs(int u,int fa){
	dp[u][0] = k[u];
	dp[u][2] = dp[u][1] = 0;
	int pos = inf,sum = 0;
	for(auto v : e[u]){
		if(v == fa) continue;
		dfs(v,u);
		dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
		dp[u][2] += min(dp[v][0], dp[v][1]);
		dp[u][1] += min(dp[v][0], dp[v][1]);
		if(dp[v][0] < dp[v][1]) ++sum;
		else pos = min(pos, dp[v][0] - dp[v][1]);
	}
	if(!sum) dp[u][1] += pos;
	return ;
}

void solve(){
	cin>>n;
	int root;
	for(int i=0; i < n; ++i){
		int id, r;
		cin >> id;
		cin >> k[id] >> m;
		while(m--){
			cin >> r;
			e[id].push_back(r);
			e[r].push_back(id);
		}
	}
	dfs(1, 0);
	cout << min(dp[1][0], dp[1][1]) << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

仅存单向边做法不推荐

//>>>Qiansui
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define mem(x,y) memset(x,y,sizeof(x))
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) cout << #x << " = " << x << " " << #y << " = "<< y << endl
//#define int long long

using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ull,ull> pull;
typedef pair<double,double> pdd;
/*

*/
const int maxm=15e2+5,inf=0x3f3f3f3f,mod=998244353;
int n, k[maxm], m;
vector<int> e[maxm];
vector<vector<int>> dp(maxm, vector<int>(3,0));

void dfs(int u){
	dp[u][0] = k[u];
	dp[u][2] = dp[u][1] = 0;
	int pos = inf;
	for(auto v : e[u]){
		dfs(v);
		dp[u][0] += min(dp[v][0], min(dp[v][1], dp[v][2]));
		dp[u][2] += min(dp[v][0], dp[v][1]);
		dp[u][1] += min(dp[v][0], dp[v][1]);
		pos = min(pos, dp[v][0] - min(dp[v][0], dp[v][1]));
	}
	dp[u][1] += pos;
	return ;
}

void solve(){
	cin>>n;
	int root;
	vector<bool> vis(n+1, false);
	for(int i=0; i < n; ++i){
		int id, r;
		cin >> id;
		cin >> k[id] >> m;
		while(m--){
			cin >> r;
			e[id].push_back(r);
			vis[r]=true;
		}
	}
	for(int i = 1; i <= n; ++i){
		if(!vis[i]){
			root=i; break;
		}
	}
	dfs(root);
	cout << min(dp[root][0], dp[root][1]) << '\n';
	return ;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _=1;
	// cin>>_;
	while(_--){
		solve();
	}
	return 0;
}

相关资料

思路来源：
https://www.luogu.com.cn/blog/Parabola/solution-p2458