P2458 90pts WA On 3 玄关求调
  • 板块题目总版
  • 楼主Tiger_Rory
  • 当前回复4
  • 已保存回复4
  • 发布时间2024/12/21 12:26
  • 上次更新2024/12/21 16:17:14
查看原帖
P2458 90pts WA On 3 玄关求调
680295
Tiger_Rory楼主2024/12/21 12:26

code:

#include <bits/stdc++.h>
using namespace std; 
const int N = 1500 + 10; 

int n, val[N];
vector<int>vec[N];
int f[N][4]; 

void dfs(int u, int fa) {
	f[u][0] = val[u]; 
	int sum = 0, minn = 1000000007;  
	for(auto i : vec[u]) {
		if(i == fa) continue; 
		dfs(i, u);   
		f[u][0] += min(min(f[i][1], f[i][0]), f[i][2]); 
		f[u][2] += min(f[i][0], f[i][1]); 
		if(f[i][0] < f[i][1]) sum++; 
		else minn = min(minn, f[i][0] - f[i][1]); 
		f[u][1] += min(f[i][0], f[i][1]);     
	}
	if(!sum) f[u][1] += minn; 
	return; 
}         

int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0), cout.tie(0); 
	cin >> n; 
	for(int i = 1; i <= n; i++) {
		int id, m, r; 
		cin >> id >> val[i] >> m; 
		for(int j = 1; j <= m; j++) {
			cin >> r; 
			vec[id].push_back(r); 
			vec[r].push_back(id); 
		} 
	}
	dfs(1, 0); 
	cout << min(f[1][0], f[1][1]); 
	return 0; 
}

2024/12/21 12:26
加载中...