HDU 6060 RXD and dividing（思维+计算贡献值）

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

题意：

给定一棵 n 个节点的树，1 为根。现要将节点 2 ~ n 划分为 k 块，使得每一块与根节点形成的最小斯坦纳树的边权值总和最大。

思路：

这道题目应该往边的贡献值方向去思考，对于u（非1）结点，设它与它父亲结点的边为e，它的子节点分的块越多，那么e这条边的贡献值也就越大，因为每一分块都需要e这条边来连通。所以我们就要尽量让每条边的贡献值都最大。

下面图解一下：（分成 3 part的情况）

4、5、6、7由于超过了3，所以只能分成3部分，我们可以假设性的分为{4,5}，{6}，{7}这样3组，1和3是没有子树关系的，所以可以把它们合并进去，不会影响3结点边的贡献值，

现在又可以假设性的分为{4,5,8}，{6,9}，{7,10}这样三组，将2结点合并进去后可以变成{4,5,8}，{2,6,9}，{7,10}这样三组，此时1、2、3、4、5、6、7、8、9这几个结点的边都已经达到了它们所能达到的最大贡献值。

依次向上分析即可。

所以，我们可以得出结论，每条边的最大贡献值就是min（sz[u]，k），最后将所有边的贡献值加起来即可。

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<cstdio>

 #include<sstream>

 #include<vector>

 #include<stack>

 #include<queue>

 #include<cmath>

 #include<map>

 #include<set>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pll;

 const int INF = 0x3f3f3f3f;

 const int maxn =  + ;

 int n, k;

 int sz[maxn];

 int val[maxn];

 vector<pll> G[maxn];

 void dfs(int u, int fa)

 {

     sz[u]=;

     for(int i=;i<G[u].size();i++)

     {

         int v=G[u][i].first;

         if(v==fa)  continue;

         val[v]=G[u][i].second;

         dfs(v,u);

         sz[u]+=sz[v];

     }

 }

 int main()

 {

     //freopen("in.txt","r",stdin);

     while(~scanf("%d%d",&n,&k))

     {

         for(int i=;i<=n;i++)  G[i].clear();

         for(int i=;i<n;i++)

         {

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             G[u].push_back(make_pair(v,w));

             G[v].push_back(make_pair(u,w));

         }

         dfs(,-);

         ll ans=;

         for(int i=;i<=n;i++)

             ans+=(ll)val[i]*min(k,sz[i]);

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西

HDU 6060 RXD and dividing（思维+计算贡献值）

最新文章

热门文章