比赛 2024暑假C班集训D 评测结果 WAATTEEEEE
题目名称 树上染色 最终得分 20
用户昵称 wzh0425 运行时间 5.117 s
代码语言 C++ 内存使用 3.34 MiB
提交时间 2024-07-13 10:50:29
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long n,k,f[105][105],g[105],vis[105],maxs;
void dfs(int cs,int x){
    if (x>n) return;
    if (cs>k){
        long long sum=0;
        for (int i=1;i<=k;i++){
            for (int j=1;j<=k;j++){
                sum+=f[g[i]][g[j]];
            } 
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (!vis[i]&&!vis[j]){
                    sum+=f[i][j];
                }
            }
        }
        maxs=max(maxs,sum);
        return;
    }
    dfs(cs,x+1);
    g[cs]=x;
    vis[x]=1;
    dfs(cs+1,x+1);
    vis[x]=0;
    g[cs]=0;
}
int main(){
    freopen("haoi2015_t1.in","r",stdin);
    freopen("haoi2015_t1.out","w",stdout);
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            f[i][j]=INT_MAX;
        }
    }
    for (int i=1;i<=n-1;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        f[a][b]=c;
        f[b][a]=c;
    }
    for (int k=1;k<=n;k++){
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (i!=j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (f[i][j]==INT_MAX){
                f[i][j]=0;
            }
        }
    }
    dfs(1,1);
    printf("%d",maxs/2);
    return 0;
}