1 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=1600; vector<int>G[N]; LL f[N][2][2],w[N]; /* 这里的 安全 表示以x为根的子树全部都安全 不安全 表示以x为根的子树除了x都安全 f[x][0][0]表示 x这个点不安全,不安装监控, f[x][0][1]表示 x这个点不安全, 安装监控, ———很明显不合理所以去除 f[x][1][0]表示 x这个点安全 ,不安装监控, f[x][1][1]表示 x这个点安全 , 安装监控, */ void dp(int x) { f[x][0][0]=0; //f[x][0][1]=w[x]; f[x][1][0]=0; f[x][1][1]=w[x]; LL t=(LL)1<<40; for(int y:G[x]) { dp(y); //1 f[x][0][0]+=f[y][1][0]; //2 //f[x][0][1]= //3 f[x][1][0]+=min(f[y][1][0],f[y][1][1]); t=min(t,f[y][1][1]-f[y][1][0]); //4 f[x][1][1]+=min(f[y][0][0],min(f[y][1][0],f[y][1][1])); } if(t>0) f[x][1][0]+=t; } int main() { int n;scanf("%d",&n); int rt=(n+1)*n/2; for(int i=1;i<=n;i++) { int x;scanf("%d",&x); scanf("%lld",&w[x]); int m;scanf("%d",&m); for(int j=1;j<=m;j++) { int y;scanf("%d",&y); G[x].emplace_back(y);rt-=y; } } dp(rt); printf("%lld",min(f[rt][1][0],f[rt][1][1])); return 0; }
- 1
信息
- ID
- 303
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 7
- 标签
- 递交数
- 305
- 已通过
- 59
- 上传者