连黄都不会了,求调QWQ(36pts)
查看原帖
连黄都不会了,求调QWQ(36pts)
1368090
ny_123457楼主2025/7/2 09:38
#include<bits/stdc++.h>
#define int long long
using namespace std;
int id,n,m,k,x,y,mark,ans,dp[15005][5];
int fa[1505],a[1505];
vector<int>son[1505];
void dfs(int p,int fath){
	int minn=1e9;
	for(int i=0;i<son[p].size();i++){
		int s=son[p][i];
		if(s==fath)continue;
		dfs(s,p);
		dp[p][0]+=min(dp[s][1],dp[s][2]);
		dp[p][1]+=min(dp[s][1],dp[s][2]);
		minn=min(minn,dp[s][2]-min(dp[s][1],dp[s][2]));
		dp[p][2]+=min(min(dp[s][0],dp[s][1]),dp[s][2]);
	}
	dp[p][2]+=a[p];
	dp[p][1]+=minn;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	a[0]=1;
 	for(int i=1;i<=n;i++){
 		a[i]=1;
 		cin>>id>>m;
 		for(int j=1;j<=m;j++){
 			cin>>x;
 			son[id].push_back(x);
 			fa[x]=1;
		}
	}
 	for(int i=0;i<n;i++){
 		if(fa[i]==0){
		 	mark=i;
			break;
		}
	}
 	dfs(mark,0);
 	cout<<min(dp[mark][2],dp[mark][1]);
    return 0;
}
2025/7/2 09:38
加载中...