2019ICPC银川网络赛 G. Factories (gym102222 G)

た入场券 2023-08-17 16:36 72阅读 0赞

其实主要是想存一下这个读入挂。。做法的话很明显 N\*100\*100的树背包，主要是儿子向父亲的转移，然后正确想法是考虑边的贡献，往上转移时这条边的贡献就是(k-j)\*j\*w，就是它子树内的工厂和外面的。然后要注意特判n=2 n=1  k=1的情况就好了。

#include<bits/stdc++.h>
    #define pb push_back
    #define ll long long
    #define mp make_pair
    #define _min(x,y) (x>=y?y:x)
    using namespace std;
    const int N=1e5+7;
    const int M=720;
    const ll inf=1e18;
    inline char nc(){
        static char buf[100000],*begin=buf,*end=buf;
        if(begin==end)begin=buf,end=buf+fread(buf,1,100000,stdin);
        if(begin==end)return EOF;
        return *begin++;
    }
    template<typename T>
    inline bool read(T &x){
        char c=nc();
        if(c==EOF)return false;
        x=0;
        while(!(c>='0'&&c<='9'||c=='-'))c=nc();
        bool flag=c=='-'?(c=nc(),1):0;
        while(c>='0'&&c<='9')x=x*10+c-'0',c=nc();
        if(flag)x=-x;
        return true;
    }
    int T;
    int n,m,k;
    ll dp[N][105];
    int cnt;
    int fir[N],nxt[N*2],to[N*2];
    ll val[N*2];
    void add_e(int x,int y,ll w){
        ++cnt;nxt[cnt]=fir[x];fir[x]=cnt;to[cnt]=y;val[cnt]=w;
        ++cnt;nxt[cnt]=fir[y];fir[y]=cnt;to[cnt]=x;val[cnt]=w;
    }
    int u,v,w;
    int du[N];
    int lef[N];
    void dfs(int x,int fa){
        //cout<<x<<"\n";
        if(du[x]==1){
            dp[x][0]=dp[x][1]=0;
            lef[x]=1;
            return;
        }
        dp[x][0]=0;
        lef[x]=0;
        for(int i=1;i<=k;i++)dp[x][i]=inf;
        for(int i=fir[x];i;i=nxt[i]){
            int v=to[i];if(v==fa)continue;
            dfs(v,x);
            lef[x]+=lef[v];
            ll qw=val[i];
            int pq=min(lef[v],k);
            for(int r=_min(lef[x],k);r>=0;r--){
                for(int j=0;j<=pq&&j<=r;j++){
                    dp[x][r]=_min(dp[x][r],dp[x][r-j]+dp[v][j]+(k-j)*j*qw);
                }
            }
        }
    
    
    }
    void init(){
        fill(fir+1,fir+1+n,0);
        fill(du+1,du+1+n,0);
        //for(int i=1;i<=n;i++)fir[i]=du[i]=lef[i]=0;
        cnt=0;
    }
    int main(){
        read(T);
        int cas=0;
        while(T--){
            read(n);read(k);init();
            for(int i=1;i<n;i++){
                read(u);read(v);read(w);
                add_e(u,v,w);
                du[u]++;du[v]++;
            }
            cout<<"Case #"<<++cas<<": ";
            if(n==1||k==1){
                cout<<0<<"\n";
                continue;
            }
            if(n==2){
                cout<<w<<"\n";
                continue;
            }
            int st=0;
            for(int i=1;i<=n;i++){
                if(du[i]!=1){st=i;break;}
            }
            dfs(st,0);
            cout<<dp[st][k]<<"\n";
        }
    }

转载于:https://www.cnblogs.com/intwentieth/p/11459249.html