5 条题解

  • 9
    @ 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]);
    }
    
    • 0
      @ 2025-7-15 15:10:18

      #include<bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; int dp[N][3],n,u,v,n1; vectorvc[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]); }

      • 0
        @ 2025-7-15 15:10:03

        #include<bits/stdc++.h> using namespace std; const int N=1e4+10; const int INF=0x3f3f3f3f; int dp[N][3],n,u,v,n1; vectorvc[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]); }

        • 0
          @ 2024-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;
          }
          
          • -2
            @ 2023-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
            标签
            递交数
            153
            已通过
            45
            上传者