求调
查看原帖
求调
657986
cstdio_luogu楼主2025/7/2 10:17

这个只过了三个点,样例没过,求调qaq

#include<bits/stdc++.h>
using namespace std;

int n;
vector<int> son[1505];
int fa[1505];
int f[1505][1];
int root;

void dfs(int x) {
	f[x][1] = 1;
	f[x][0] = 0;
	if(son[x].size() == 0) return;
	for(int i = 0; i < son[x].size(); i++) {
		dfs(son[x][i]);
		f[x][1] += min(f[son[x][i]][1],f[son[x][i]][0]);
		f[x][0] += f[son[x][i]][1];
	}
}

int main() {
	cin >> n;
	memset(fa,-1,sizeof(fa)); 
	for(int i = 1; i <= n; i++) {
		int x;
		cin >> x;
		int k;
		cin >> k;
		for(int j = 1; j <= k; j++) {
			int a;
			cin >> a;
			son[x].push_back(a);
			fa[a] = x;
		}
	} 
	for(int i = 0; i < n; i++) {
		if(fa[i] == -1) {
			root = i;
			break;
		}
	}
//	cout << root << endl;
	dfs(root);
	cout << min(f[root][1],f[root][0]);
}
2025/7/2 10:17
加载中...