比赛 2024暑假C班集训D 评测结果 WWWTTEEEEE
题目名称 树上染色 最终得分 0
用户昵称 Untitled 运行时间 6.451 s
代码语言 C++ 内存使用 3.39 MiB
提交时间 2024-07-13 11:18:37
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

int n,k;
long long f[110][110];
bool c[110];
long long res;

long long judge(){
    long long cnt=0;
    for (int i=1;i<=n;i++){
        for (int j=i+1;j<=n;j++){
            if (c[i]==c[j]) cnt+=f[i][j];
        }
    }
    return cnt;
}

void dfs(int x,int v){
    if (x>n){
        long long h=judge();
        if (h>res) res=h;
        return;
    }
    if (n-x+1==v){
        c[x]=1;
        dfs(x+1,v-1);
    }
    else{
        c[x]=1;
        dfs(x+1,v-1);
        c[x]=0;
        dfs(x+1,v);
    }
    return;
}

int main(){
    freopen("haoi2015_t1.in","r",stdin);
    freopen("haoi2015_t1.out","w",stdout);
    
    int a,b;
    long long v;
    scanf("%d %d",&n,&k);
    memset(f,0x3f,sizeof(f));
    for (int i=1;i<n;i++){
        scanf("%d %d %lld",&a,&b,&v);
        f[a][b]=v,f[b][a]=v;
        f[i][i]=0;
    }
    f[n][n]=0;
    for (int x=1;x<=n;x++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++) if (f[i][x]+f[x][j]<f[i][j]) f[i][j]=f[i][x]+f[x][j];
        }
    }
    dfs(1,k);
    printf("%lld",res/2);
    
    
    return 0;
}