3 条题解

  • 10
    @ 2023-8-9 10:27:47
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e4+10;
    const int INF=0x3f3f3f3f;
    int dp[N][3],n,u,v,n1;
    vector<int>vc[N];
    void dfs(int u,int fa){
    	bool flag=0;
    	int minn=INF;
    	for(int i=0;i<vc[u].size();i++){
    		int v=vc[u][i];
    		if(v==fa)continue;
    		dfs(v,u);
    		dp[u][0]+=min(dp[v][0],min(dp[v][1],dp[v][2]));
    		dp[u][2]+=min(dp[v][0],dp[v][1]);
    		dp[u][1]+=min(dp[v][0],dp[v][1]);
    		minn=min(minn,dp[v][0]-min(dp[v][0],dp[v][1]));
    	}
    	dp[u][1]+=minn;
    }
    int main(){
    	cin>>n;
    	for(int i=1;i<=n;i++){
    		cin>>u;
    		cin>>dp[u][0];
    		cin>>n1;
    		for(int j=1;j<=n1;j++){
    			cin>>v;
    			vc[u].push_back(v);
    			vc[v].push_back(u);
    		}
    	}
    	dfs(1,0);
    	cout<<min(dp[1][0],dp[1][1]);
    }
    

    信息

    ID
    474
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    151
    已通过
    43
    上传者