2. 科研基地
题目ID：20445 必做题文件 操作100分
时间限制: 1000ms
空间限制: 524288kB
输入文件名: center.in
输出文件名: center.out
题目描述
在一个庞大的科研基地中，研究人员需要定期巡检不同的实验室和设备节点。这个基地中一共有nn个实验室，它们通过n−1n−1条通道相互连接。第ii条通道连接着aiai和bibi两个实验室，需要titi的时间通过该条通道。
每天晚上值班人员都要对基地内部的实验室进行巡检。值班人员可以从任意一个实验室出发开始巡查，并在巡查结束后回到出发点。由于夜晚的时间有限，值班人员不需要巡查完所有的实验室，只要保证未被巡查的实验室个数不超过KK(K≤20K≤20)个。
今天晚上轮到小C值班，他想知道他最少需要多长时间来完成巡查任务。
输入格式
从文件center.in中读入数据。
第一行包含两个整数nn, KK, 分别表示实验室的个数和未被巡查的实验室个数的最大值。
接下来的n−1n−1行每行包含三个整数aa,bb,tt，表示在aa和bb之间存在一条耗时为tt的通道。
输出格式
输出到文件center.outcenter.out中。
输出一个整数表示完成巡查任务最少需要的时间。
样例
Input 1
7 3 3 2 30 3 4 47 3 6 90 6 7 84 2 5 68 2 1 67
Output 1
288
Input 2
10 5 9 7 29 7 5 46 7 6 32 5 1 11 7 2 44 2 4 99 7 10 30 2 8 60 7 3 9
Output 2
190
Input 3
见下发文件中的center/center1.in
Output 3
见下发文件中的center/center1.out
Input 4
见下发文件中的center/center2.in
Output 4
见下发文件中的center/center2.out
数据范围
| 数据点 | 特殊限制 |
|---|---|
| 1 - 4 | n≤20n≤20 |
| 5 - 6 | K = 0 |
| 7 - 8 | K = 1 |
| 9-10 | K = 2 |
| 11 - 20 | 无特殊限制 |
对于所有数据，保证n≤104,0≤K≤min(n−1,20),ti≤106n≤104,0≤K≤min(n−1,20),ti≤106。
代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN = 1e4 + 10;
ll n = 0,k = 0,sum = 0;
ll out[MAXN];
struct node
{
ll father;
ll val;
bool flag;
} a[MAXN];
int main()
{
freopen("center.in","r",stdin);
freopen("center.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
memset(out,0,sizeof(0));
if(k == 0)
{
for(ll i = 1; i < n; i++)
{
ll ui,vi,di;
cin >> ui >> vi >> di;
a[vi].val = di;
sum += di;
}
cout << 2 * sum << "\n";
return 0;
}
else
{
for(ll i = 1; i < n; i++)
{
ll ui,vi,di;
cin >> ui >> vi >> di;
a[vi].val = di;
a[vi].father = ui;
sum += di;
a[i].flag = false;
out[ui]++;
}
/*
cout << sum << "\n";
for(int i = 1; i <= n; i++)
{
cout << out[i] << "\n";
}
*/
for(ll i = 1; i <= k; i++)
{
int id = 0;
int maxx = INT_MIN;
for(ll j = 1; j <= n; j++)
{
if(out[j] == 0 && a[j].flag == false)
{
if(maxx < a[j].val)
{
maxx = a[j].val;
id = j;
}
}
}
sum -= maxx;
out[a[id].father]--;
a[id].flag = true;
}
}
cout << 2 * sum << "\n";
return 0;
}
求救QwQ
