比赛 |
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;
}