2017多校3 1005 RXD and dividing

本文主要是介绍2017多校3 1005 RXD and dividing，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.hdu.edu.cn/showproblem.php?pid=6060

求一棵树中从2-n的点分成k部分，求每一部分加上1这个根节点的最小生成树长度和的最大值。

可以理解成求每条边的贡献，最大边肯定是选择越多越好，那么我们就可以去寻找每一个根节点下的节点数与k的比较，如果k小，那该根节点的边就可以认为会贡献k次，如果是节点数小，那么就是过节点数次，dfs去寻找节点数就可以了。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const long long int  N=10000007;
struct node{int  en;int v;int next;
}e[N];
int  n,k;
int  cnt;
int  _hash[N];
long long int  ans;
void _push(int  op,int  ed,int  cost)
{e[++cnt].en=ed;e[cnt].v=cost;e[cnt].next=_hash[op];_hash[op]=cnt;    
}
int  find(int op,int ed,int cost)
{int i;int  sum=1;for(i=_hash[ed];i;i=e[i].next){int too=e[i].en;if(too!=op)sum+=find(ed,too,e[i].v); }if(sum>k)ans+=(long long int )cost*k;else ans+=(long long int)cost*sum;return sum;
}
int main(){while(~scanf("%d%d",&n,&k)){ans=0;cnt=0;int  op,ed,cost;int i;memset(_hash,0,sizeof(_hash));for(i=1;i<n;i++){scanf("%d%d%d",&op,&ed,&cost);_push(op,ed,cost);_push(ed,op,cost);}find(0,1,0);printf("%lld\n",ans);}return 0;
}

这篇关于2017多校3 1005 RXD and dividing的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---