3 条题解
-
10庄力 (zhuangli2018) LV 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]); }
-
02024-3-24 16:38:30@
/************************************ Note Book: ************************************/ #include <iostream> #include <cstdio> #include <iomanip> #include <cmath> #include <algorithm> #include <cstring> #include <string> #include <stack> #include <map> #include <queue> #include <math.h> #define LL long long using namespace std; const int INF = 0x3f3f3f3f; const int N = 1e5 + 10; int n ; vector<int > p[N]; int num[N]; bool vis[N]; int dp[N][3]; void dfs(int id , int fa) { int d = INF; for(int i = 0; i < p[id].size(); i++) { int son = p[id][i]; if(son == fa) { continue; } dfs(son , id); dp[id][0] += min(dp[son][1] , dp[son][2]); dp[id][1] += min(dp[son][2] , min(dp[son][1] , dp[son][0])); dp[id][2] += min(dp[son][2] , dp[son][1]); d = min(d , dp[son][1] - min(dp[son][2] , dp[son][1])); } dp[id][2] += d; dp[id][1] += num[id]; } int main() { cin >> n ; for(int i = 0; i < n ; i++) { int id; cin >> id; cin >> num[id]; int t; cin >> t; while( t-- ) { int x; cin >> x; p[id].push_back(x); p[x].push_back(id); } } int root = 0; for(int i = 1; !root && i <= n; i++) { if(!vis[i]) { root = i; } } dfs(root , -1); cout << min(dp[root][2] , dp[root][1]) << endl; return 0; }
-
-22023-4-25 19:42:25@
#include<bits/stdc++.h> #define ll long long #define R register using namespace std; const int N=1e5+85; struct E{ int nxt,to; }e[N]; int n,num,head[N],rot[N],val[N],root=1,f[N][3]; inline void add(R int u,R int v){ e[++num].to=v; e[num].nxt=head[u]; head[u]=num; } // 监控T的子树 不放0 // 可以不监控 不放1 // 监控T的子树 放 2 inline void dp(R int pos,R int fa){ f[pos][2]=val[pos]; R int pd=1,vis=1,cha=0x3f3f3f3f; for(R int i=head[pos];i;i=e[i].nxt){ R int v=e[i].to; if(v!=fa){ pd=0; dp(v,pos); if(f[v][0]>=f[v][2]){ f[pos][0]+=f[v][2]; vis=0; } else{ f[pos][0]+=f[v][0]; cha=min(cha,f[v][2]-f[v][0]); } f[pos][1]+=min(f[v][0],f[v][2]); f[pos][2]+=min(f[v][0],min(f[v][1],f[v][2])); } } if(vis&&pd==0) f[pos][0]+=cha; if(pd){ f[pos][0]=val[pos]; f[pos][1]=0; f[pos][2]=val[pos]; } } int main(){ scanf("%d",&n); for(R int i=1;i<=n;++i){ R int p,m,w; scanf("%d%d%d",&p,&w,&m); val[p]=w; for(R int j=1;j<=m;++j){ R int k; scanf("%d",&k); add(k,p);add(p,k); rot[k]=1; } } while(rot[root])root++; dp(root,0); printf("%d",min(f[root][0],f[root][2])); return 0; }
- 1
信息
- ID
- 474
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 151
- 已通过
- 43
- 上传者