rt。建完图以后就是用的P2014 [CTSC1997] 选课的代码。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=205;
int n,m;
int a[N],in[N],siz[N];
int dp[N][N];
string s,s1,s2;
vector<string>tmp[N];
vector<int>v[N];
map<string,int>mp;
void init(){
	mp.clear();
	for(int i=1;i<=n;i++)
		tmp[i].clear(),v[i].clear();
	s.clear(),s1.clear(),s2.clear();
	memset(a,0,sizeof(a));
	memset(in,0,sizeof(in));
	memset(siz,0,sizeof(siz));
	memset(dp,0x3f,sizeof(dp));
	return;
}
void DFS(int x){
	siz[x]=1,dp[x][1]=bool(!in[x])*a[x];
	for(int i=0;i<v[x].size();i++){
		int to=v[x][i];
		DFS(to);
		siz[x]+=siz[to];
		for(int j=min(m+1,siz[x]);j>=0;j--)
			for(int k=0;k<=min(siz[to],j-1);k++)
				dp[x][j]=min(dp[x][j],dp[x][j-k]+dp[to][k]);
	}
	return;
}
signed main(){
	while(1){
		init();
		getline(cin,s);
		if(s=="#")
			break;
		stringstream str1;
		str1<<s;
		str1>>n>>m;
		for(int i=1;i<=n;i++){
			getline(cin,s);
			stringstream str2;
			str2<<s;
			str2>>s1>>a[i];
			mp[s1]=i;
			while(str2>>s2)
				tmp[mp[s1]].push_back(s2);
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<tmp[i].size();j++){
				v[i].push_back(mp[tmp[i][j]]);
				in[mp[tmp[i][j]]]++;
			}
		}
		for(int i=1;i<=n;i++)
			if(!in[i])
				v[0].push_back(i);
		DFS(0);
		cout<<dp[0][m+1]<<"\n";
	}
	return 0;
}