题目
RXD and dividing
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others) Total Submission(s): 1509 Accepted Submission(s): 653
Problem Description
RXD has a tree
T
, with the size of
n
. Each edge has a cost.
Define
f(S)
as the the cost of the minimal Steiner Tree of the set
S
on tree
T
.
he wants to divide
2,3,4,5,6,…n
into
k
parts
S1,S2,S3,…Sk
,
where
⋃Si={2,3,…,n}
and for all different
i,j
, we can conclude that
Si⋂Sj=∅
.
Then he calulates
res=∑ki=1f({1}⋃Si)
.
He wants to maximize the
res
.
1≤k≤n≤106
the cost of each edge∈[1,105]
Si
might be empty.
f(S)
means that you need to choose a couple of edges on the tree to make all the points in
S
connected, and you need to minimize the sum of the cost of these edges.
f(S)
is equal to the minimal cost
Input
There are several test cases, please keep reading until EOF.
For each test case, the first line consists of 2 integer
n,k
, which means the number of the tree nodes , and
k
means the number of parts.
The next
n−1
lines consists of 2 integers,
a,b,c
, means a tree edge
(a,b)
with cost
c
.
It is guaranteed that the edges would form a tree.
There are 4 big test cases and 50 small test cases.
small test case means
n≤100
.
Output
For each test case, output an integer, which means the answer.
Sample Input
5 4
1 2 3
2 3 4
2 4 5
2 5 6
Sample Output
27
题目大意
给你n个点，要求你把[2-n]分成k个部分，然后每一部分最后和1连通， 计算每一部分的权重和，最后求k部分的所有权重和， 现在让我们求怎么分才能使得最后的权重和最大
解题思路
看完题解之后感觉突然明白了，其实根本没必要去管怎么去分成k部分，我们只需要保证每条边最大限度的被使用就可以了
如图，我们只需要让a这条边走min(size[2],k)就可以，看图就可以知道a最多被走size[2]次，因为每个集合是不重复的，不可能一个点被用两次，但是还不能超过k次
所以一遍dfs就可以，只需要记录该点的size和他到父节点的权重
下面贴上代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define read(a) scanf("%d",&a)
const int maxn=1e6+10;
int siz[maxn];
int pre[maxn];
int n,k;
struct tree
{
int v;
int cost;
tree(){}
tree(int a,int b):v(a),cost(b){}
};
vector<tree> e[maxn];
void dfs(int x,int fa)
{
siz[x]=1;
for(auto &y:e[x])
{
if(y.v==fa)
continue;
dfs(y.v,x);
pre[y.v]=y.cost;
siz[x]+=siz[y.v];
}
}
void work()
{
int x,y,z;
memset(siz,0,sizeof(siz));
memset(pre,0,sizeof(siz));
for(int i=1;i<=n;i++)
e[i].clear();
for(int i=1;i<n;i++)
{
read(x);read(y);read(z);
e[x].push_back(tree(y,z));
e[y].push_back(tree(x,z));
}
dfs(1,-1);
LL ans=0;
/* for(int i=1;i<=n;i++)
{
cout<<i<<" pre "<<pre[i]<<" siz "<<siz[i]<<endl;
}*/
for(int i=1;i<=n;i++)
{
// int a=pre[i]*min(siz[i],k);
// cout<<a<<endl;
ans+=1LL*(LL)pre[i]*(LL)min(siz[i],k);
}
printf("%lld\n",ans);
}
int main()
{
while(~scanf("%d %d",&n,&k))
{
work();
}
return 0;
}
