std

std 2022-07-04 17:34:29 2022-07-05 17:53:44 5 返回题目

Sample A

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

const int N = 3010;

int n,m,tot;
int f[N][3],fa[N];
int h[N],nxt[N],to[N];

void add(int x,int y) {
	to[++tot]=y;
	nxt[tot]=h[x];
	h[x]=tot;
}

void init() {
	int a,b,x;
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		scanf("%d %d",&a,&b);
		for(int j=1; j<=b; j++) {
			scanf("%d",&x);
			add(a,x);
			fa[x]=a;
		}
	}
}

void dfs(int u) {
	f[u][1]=1;//f[u][1]:以u为根的子树,在u结点放士兵时子树上最小花费
	for(int i=h[u]; i; i=nxt[i]) {
		int v=to[i];
		dfs(v);
		f[u][1]+=min(f[v][0],f[v][1]);
		f[u][0]+=f[v][1];//f[u][0]:以u为根的子树,不在u结点放士兵时子树上最小花费
	}
}

void work() {
	int r=0;//注意点编号从0开始
	while (fa[r]>0) r++;
	dfs(r);
	printf("%d\n",min(f[r][0],f[r][1]));
}

int main() {
	init();
	work();
	return 0;
}

Sample B

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int num[2100],f[2100][3],fa[2100];
vector<int> son[2100];
void dfs(int u) {
	f[u][1]=1;
	for(int i=0; i<son[u].size(); i++) {
		int v=son[u][i];
		dfs(v);
		f[u][0]+=f[v][1];
		f[u][1]+=min(f[v][0],f[v][1]);
	}
}
int main() {
	int n; 
	scanf("%d",&n);
	for(int i=1; i<=n; i++) {
		int m; 
		scanf("%d",&m);
		m++;
		scanf("%d",&num[m]);
		for(int j=1; j<=num[m]; j++) {
			int r;
			scanf("%d",&r);
			son[m].push_back(++r);
			fa[r]=m;
		}
	}
	int root=1;
	while(fa[root]) root++;
	dfs(root);
	printf("%d\n",min(f[root][0],f[root][1]));
	return 0;
}
{{ vote && vote.total.up }}