题目分析

本题描述了一个通过钻石贿赂获取选票的问题，可以抽象为树形动态规划问题：

1. 问题核心：给定一棵树结构，每个节点有贿赂成本，选择若干节点使得其子树覆盖的节点数≥m，求最小总成本
2. 关键特征：
   • 统治关系形成森林结构（多棵树）
   • 贿赂一个国家会获得其所有属国的选票
   • 需要至少获得m张选票

解题思路

1. 数据结构：

   • 使用邻接表存储树结构（统治关系）
   • 哈希表映射国家名称到节点ID
   • 动态规划数组f[u][k]表示以u为根的子树获得k票的最小成本

2. 算法选择：

   • 树形DP：后序遍历计算子树信息
   • 分组背包：处理子节点的不同选择方案

3. 关键步骤：

   • 构建统治关系树（森林）
   • 添加虚拟根节点0连接所有树根
   • 递归计算每个子树的选择方案
   • 合并子节点方案时使用逆向DP更新

标准代码（C++）

//STATUS:C++_AC_16MS_588KB
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<map>
using namespace std;
#define LL __int64
#define pii pair<int,int>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int N=300,INF=0x3f3f3f3f,MOD=100000000;
const double DNF=100000000000;

struct Edge{
	int u,v;
}e[N];

int nextEdge[N],first[N],vis[N],f[N][N],cost[N],cnt[N];
int n,m,mt;

void adde(int u,int v)
{
	e[mt].u=u,e[mt].v=v;
	nextEdge[mt]=first[u],first[u]=mt++;
}

void dfs(int u)
{
	int i,j,v;
	f[u][0]=0;
	i=first[u];
	if(i==-1){
		f[u][1]=cost[u];
		cnt[u]=1;
		return;
	}
	for(;i!=-1;i=nextEdge[i]){
		dfs(e[i].v);
		cnt[u]+=cnt[e[i].v];
		for(v=cnt[u];v>=0;v--){
			for(j=0;j<=v;j++){
				f[u][v]=Min(f[u][v],f[u][v-j]+f[e[i].v][j]);
			}
		}
	}
	f[u][++cnt[u]]=cost[u];
}

int main()
{
	//   freopen("in.txt","r",stdin);
	int i,j,a,k,kt,ans,id,idfa;
	char s[110],cs[N*110];
	map<string,int> q;
	while(fgets(s, sizeof(s), stdin) != NULL)
	{
		if(s[0]=='#')break;
		q.clear();
		mem(first,-1);
		mem(f,INF);
		mem(vis,0);mem(cnt,0);
		mt=0;
		ans=INF;
		sscanf(s,"%d%d",&n,&m);
		for(i=1,id=0;i<=n;i++){
			scanf("%s%d",s,&a);
			if(!q[s])q[s]=++id;
			idfa=q[s];
			cost[idfa]=a;
			fgets(cs, sizeof(cs), stdin);
			if(!cs[0])continue;
			for(k=1,j=0;1;k++,j++){
				if(cs[k]==' ' || cs[k]=='\0'){
					s[j]='\0';
					if(!q[s])q[s]=++id;
					kt=q[s];
					vis[kt]=1;
					adde(idfa,kt);
					j=-1;
					if(cs[k]=='\0')break;
				}
				else s[j]=cs[k];
			}
		}
		for(i=1;i<=n;i++){
			if(vis[i])continue;
			adde(0,i);
		}
		
		dfs(0);
		for(i=m;i<=n;i++)
			if(f[0][i]<ans)ans=f[0][i];
		
		printf("%d\n",ans);
	}
	return 0;
}

代码解析

1. 输入处理：

   • 使用getline读取整行输入
   • 解析国家名称、钻石数量和属国列表
   • 使用哈希表country_id建立名称到ID的映射

2. 树构建：

   • 识别根节点（没有父节点的国家）
   • 添加虚拟根节点0连接所有真实根节点

3. 动态规划：

   • f[u][k]表示以u为根的子树获得k票的最小成本
   • 递归处理子节点后，使用分组背包思想合并子节点方案
   • 逆向更新保证每个子节点只被考虑一次

4. 结果查询：

   • 在虚拟根节点的DP结果中查询≥m票的最小成本

该解法时间复杂度为O(n^3)，适用于题目给定的n≤200的数据规模，能够高效解决问题。