90分求助
查看原帖
90分求助
400201
WuyanruVR楼主2021/5/10 21:30

不知道哪里错了,求助各位大神。

#include<cstring>
#include<cstdio>
#include<vector>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define Min(a,b,c) (min(min(a,b),c))
using namespace std;
bool vis[10001][3];
int dp[10001][3];
vector<int>s[10001];
int a[10001];
int n;
int dfs(int num,int k) {
	if(vis[num][k])
		return dp[num][k];
	vis[num][k]=1;
	if(k==0) {//父节点上放了一个保安
		dp[num][k]=0;
		for(unsigned i=0; i<s[num].size(); i++)
			dp[num][k]+=min(dfs(s[num][i],2),dfs(s[num][i],1));
		dp[num][k]=min(dp[num][k],dfs(num,2));
	} else if(k==1) {//任意子节点放一个保安
		if(s[num].size()==0)
			return dp[num][k];
		dp[num][k]=0;
		int sonnum=0;
		int min=0x3f3f3f3f;
		for(unsigned i=0; i<s[num].size(); i++) {
			int shao=dfs(s[num][i],1);
			int duo=dfs(s[num][i],2);
			min=min(min,duo-shao);
			if(duo<=shao) {
				sonnum++;
				dp[num][k]+=duo;
			} else
				dp[num][k]+=shao;
		}
		if(sonnum==0)
			dp[num][k]+=min;
	} else {//节点上放一个保安
		dp[num][k]=a[num];
		for(unsigned i=0; i<s[num].size(); i++)
			dp[num][k]+=Min(dfs(s[num][i],0),dfs(s[num][i],1),dfs(s[num][i],2));
	}
	return dp[num][k];
}
int main() {
	memset(dp,0x3f,sizeof(dp));
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
	    int in,num;
	    scanf("%d",&in);
	    scanf("%d%d",a+in,&num);
	    for(int i=1;i<=num;i++)
	    {
	        int p;
	        scanf("%d",&p);
            s[in].push_back(p);
        }
    }
	printf("%d\n",min(dfs(1,2),dfs(1,1)));
	return 0;
}
2021/5/10 21:30
加载中...