HDU-6060 RXD and dividing - 2017 Multi-University Training Contest - Team 3(思维+最小斯坦纳树)
题意：
n个节点的树，要求将除1节点外的所有节点分成k个集合，然后再将每个集合并上1号节点，定义每一集合值value为其中的点在原图上的最小斯坦纳树，然后问所有集合的value和最大可能是多少。
思路：
"根据最小斯坦纳树的定义, (x,fax)这条边的贡献是x子树内不同标号的个数目difi.那么显然有difi≤min(k,szi),szi表示子树大小"摘自官方题解。所以我们求出所有边可以贡献的次数，答案就等于所有的(边权值*min(贡献次数,k)的和。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6+5;
struct node
{
int v, w, next;
} edge[maxn*2];
int no, head[maxn];
int n, k;
int cnt[maxn];
LL ans;
inline void init()
{
no = 0;
memset(head, -1, sizeof head);
}
inline void add(int u, int v, int w)
{
edge[no].v = v; edge[no].w = w;
edge[no].next = head[u]; head[u] = no++;
}
void dfs(int cur, int father, int val)
{
cnt[cur] = 1;
for(int i = head[cur]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(v == father) continue;
dfs(v, cur, edge[i].w);
cnt[cur] += cnt[v];
}
ans += 1ll*val*min(cnt[cur], k);
}
int main()
{
while(~scanf("%d %d", &n, &k))
{
init();
for(int i = 1; i < n; ++i)
{
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
ans = 0;
dfs(1, -1, 0);
printf("%lld\n", ans);
}
return 0;
}
继续加油~