3 条题解

  • 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]);
    }
    
    • 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
        标签
        递交数
        151
        已通过
        43
        上传者