90 分求助
查看原帖
90 分求助
361141
_JF_殉情楼主2022/10/3 22:34
#include<bits/stdc++.h>
using namespace std;
const int N =1e6+10;
vector<int> g[N<<1];
int dp[N<<1][3],c[N],in[N];
void dfs(int node,int fath)
{
	dp[node][1]=c[node],dp[node][2]=INT_MAX;
	int sum=0;
	for(int i=0;i<g[node].size();i++)
	{
		int v=g[node][i];
		if(v==fath)
			continue;
		dfs(v,node);
		dp[node][0]+=min(dp[v][1],dp[v][2]);
		dp[node][1]+=min(min(dp[v][0],dp[v][1]),dp[v][2]);
		sum+=min(dp[v][1],dp[v][2]);
	}
	for(int i=0;i<g[node].size();i++)
	{	
		int v=g[node][i],minn=min(dp[v][1],dp[v][2]);
		if(v==fath)
			continue;
		dp[node][2]=min(dp[node][2],sum-minn+dp[v][1]);
	}
}
int main()
{
	//memset(dp,N,sizeof(dp));
	int n;
	cin>>n;
	for(int i=1,u,v,t;i<=n;i++)
	{
		cin>>u>>c[i]>>t;
		while(t--)
			cin>>v,g[u].push_back(v),g[v].push_back(u),in[v]=1; 
	}
	int root;
	for(int i=1;i<=n;i++)
		if(in[i]==0)
			root=i;
	dfs(root,0);
	cout<<min(dp[root][1],dp[root][2]); 
}

2022/10/3 22:34
加载中...