20分的代码,有什么问题吗??求调!!!
查看原帖
20分的代码,有什么问题吗??求调!!!
1191361
daixihan楼主2025/7/26 10:36
#include<bits/stdc++.h>
using namespace std;
const int N=1505;
vector<int> G[N];
int n,m,x,y,a[N],d[N],r,f[N][3],ans=1e9;
void dfs(int x){
	f[x][0]=a[x];
	int minn=1e9,flag=1;
	for(auto y:G[x]){
		dfs(y);
		f[x][0]+=min(f[y][1],min(f[y][0],f[y][2]));
		f[x][1]+=min(f[y][0],f[y][2]);
		if(f[y][0]>f[y][1]){
			f[x][2]+=f[y][1];
			minn=min(minn,f[y][0]-f[y][1]);
		}
		else{
			f[x][2]+=f[y][0];
			flag=0;
		}
	}
	if(flag) f[x][2]+=minn;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		cin>>a[x]>>m;
		for(int j=1;j<=m;j++){
			cin>>y;
			G[x].push_back(y);
			d[y]++;
		}
	}
	for(int i=1;i<=n;i++){
		if(!d[i]){
			r=i;
			break;
		}
	}
	dfs(r);
	ans=min(f[r][0],f[r][2]);
	cout<<ans;
	return 0;
}
2025/7/26 10:36
加载中...