bzoj 4033 树上染色 - 树形动态规划

　　有一棵点数为N的树，树边有边权。给你一个在0~N之内的正整数K，你要在这棵树中选择K个点，将其染成黑

色，并将其他的N-K个点染成白色。将所有点染色后，你会获得黑点两两之间的距离加上白点两两之间距离的和的

收益。问收益最大值是多少。

Input

第一行两个整数N,K。

接下来N-1行每行三个正整数fr,to,dis，表示该树中存在一条长度为dis的边(fr,to)。

输入保证所有点之间是联通的。

N<=2000,0<=K<=N

Output

输出一个正整数，表示收益的最大值。

Sample Input

Sample Output

17

【样例解释】

将点1,2染黑就能获得最大收益。

　　动态规划的第一步——设计状态，f[i][j]表示以i节点为根的子树中染了j个黑点的"收益"。

　　不过这样没有黑点的位置，这么多个点，总不可能用N进制来表示点的位置。所以只能换个思路。

　　对于当前考虑的这棵子树，我知道染了j个节点，那么我知道在这棵子树内的白点数和子树外的白点数和黑点数。因此我可以计算出节点i到它的父节点的那条边的对答案的贡献，对于子节点转移到父节点就是一个用dp合并的过程，因此解决了状态转移的问题，时间复杂度为O(nk)。

　　注意dp时不合法的状态一定不能转移（看代码吧，或者自己想想也可以，状态转移前有个if）

　　(现在觉得以前的树归写得好丑)

Code

 /**

  * bzoj

  * Problem#4033

  * Accepted

  * Time:630ms

  * Memory:17092k

  */

 #include<iostream>

 #include<fstream>

 #include<sstream>

 #include<algorithm>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<cctype>

 #include<cmath>

 #include<ctime>

 #include<map>

 #include<stack>

 #include<set>

 #include<queue>

 #include<vector>

 #ifndef WIN32

 #define AUTO "%lld"

 #else

 #define AUTO "%I64d"

 #endif

 using namespace std;

 typedef bool boolean;

 #define inf 0xfffffff

 #define smin(a, b) (a) = min((a), (b))

 #define smax(a, b) (a) = max((a), (b))

 template<typename T>

 inline boolean readInteger(T& u) {

     char x;

     int aFlag = ;

     while(!isdigit((x = getchar())) && x != '-' && x != -);

     if(x == -)    {

         ungetc(x, stdin);

         return false;

     }

     if(x == '-') {

         aFlag = -;

         x = getchar();

     }

     for(u = x - ''; isdigit((x = getchar())); u = u *  + x - '');

     u *= aFlag;

     ungetc(x, stdin);

     return true;

 }

 ///map template starts

 typedef class Edge{

     public:

         int end;

         int next;

         int w;

         Edge(const int end = , const int next = , const int w = ):end(end), next(next), w(w){}

 }Edge;

 typedef class MapManager{

     public:

         int ce;

         int *h;

         Edge *edge;

         MapManager(){}

         MapManager(int points, int limit):ce(){

             h = new int[(const int)(points + )];

             edge = new Edge[(const int)(limit + )];

             memset(h, , sizeof(int) * (points + ));

         }

         inline void addEdge(int from, int end, int w){

             edge[++ce] = Edge(end, h[from], w);

             h[from] = ce;

         }

         inline void addDoubleEdge(int from, int end, int w){

             addEdge(from, end, w);

             addEdge(end, from, w);

         }

         Edge& operator [] (int pos) {

             return edge[pos];

         }

 }MapManager;

 #define m_begin(g, i) (g).h[(i)]

 ///map template ends

 template<typename T>class Matrix{

     public:

         T *p;

         int lines;

         int rows;

         Matrix():p(NULL){    }

         Matrix(int rows, int lines):lines(lines), rows(rows){

             p = new T[(lines * rows)];

         }

         T* operator [](int pos){

             return (p + pos * lines);

         }

 };

 #define matset(m, i, s) memset((m).p, (i), (s) * (m).lines * (m).rows)

 int n, k;

 MapManager g;

 Matrix<long long> f;

 int* size;

 inline void init() {

     readInteger(n);

     readInteger(k);

     g = MapManager(n,  * n);

     f = Matrix<long long>(n + , k + );

     size = new int[(const int)(n + )];

     matset(f, , sizeof(long long));

     for(int i = , a, b, c; i < n; i++) {

         readInteger(a);

         readInteger(b);

         readInteger(c);

         g.addDoubleEdge(a, b, c);

     }

 }

 void treedp(int node, int fa, int len) {

     size[node] = ;

     for(int i = m_begin(g, node); i != ; i = g[i].next) {

         int& e = g[i].end;

         if(e == fa)     continue;

         treedp(e, node, g[i].w);

         size[node] += size[e];

         for(int j = min(size[node], k); j >= ; j--) {

             for(int s = ; s <= size[e] && s <= j; s++) {

                 if(j - s <= size[node] - size[e])

                     smax(f[node][j], f[node][j - s] + f[e][s]);

             }

         }

     }

     for(int i = ; i <= min(size[node], k); i++)

             f[node][i] += (i * 1LL * (k - i) + (size[node] - i) * 1LL * (n - k - size[node] + i)) * len;

 }

 inline void solve() {

     treedp(, , );

     printf(AUTO"\n", f[][k]);

 }

 int main() {

     init();

     solve();

     return ;

 }

巴特西

bzoj 4033 树上染色 - 树形动态规划

Code

最新文章

热门文章