/*  Name: 修剪花卉  Copyright:   Author:   Date: 26-11-06 22:29  Description: 修剪花卉内存限制：32M 问题背景： ZZ对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。 于是当日课后，ZZ就向老师提出了这个问题： 一株奇怪的花卉，上面共连有N朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。 每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。 所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。 经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。 老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那朵）花卉上所有花朵的“美丽指数”之和最大。 老师想了一会儿，给出了正解（交大的老师是很牛的~）。ZZ见问题被轻易攻破，相当不爽，于是又拿来问你。 输入说明： 第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N朵花。 第二行有N个整数，第I个整数表示第I朵花的美丽指数。 接下来N-1行每行两个整数a,b，表示存在一条连接第a朵花和第b朵花的枝条。 输出说明： 一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。 样例输入： 7 -1 -1 -1 1 1 1 0 1 4 2 5 3 6 4 7 5 7 6 7 样例输出： 3 数据范围： 对于60%的数据， 保证N≤1,000 对于100%的数据，保证N≤16,000 */ /*算法：先把所有的花进行分组，把连在一起的花合并到一组，那么问题就转化为求每一组中数据之和的最大值。合并花的算法借鉴了连通问题。 */ #include <iostream> using namespace std; const int N = 20000; void Connected(int id[], int p, int q);int MaxSum(const int data[], int id[]); int main()  { //////////此部分由用户输入数据测试代码/////////////////// int data[N+1] = {0};// cout << "enter data:" << endl;// for (int i=1; i<=N; i++)//     cin >> data[i];// //    int id[N+1];//    for (int i=0; i<=N; i++)//     id[i] = i;//    //    fflush(stdin);// cout << "enter blunch:" << endl; //    int p, q;//    int i = 1;//    while (i < N)//    { //  cin >> p >> q;//  Connected(id, p, q);//  i++;// }///////////////////////////////////////////////// /////////此部分由计算机产生大量随机数测试代码////////////////// int data[N+1] = {0}; for (int i=1; i<=N; i++) //美丽指数分布在-10到10之间      data[i] = rand()%21 - 10;// // for (int i=1; i<=N; i++)//  cout << data[i] << ' ';// cout << endl;     int id[N+1];    for (int i=0; i<=N; i++)     id[i] = i;     int p, q;    int i = 1;    while (i < N) {  p = rand() % N + 1;  q = rand() % N + 1;  if (p == q)   continue;//  cout << p << ' ' << q << "\t";  Connected(id, p, q);  i++; }// /////////////////////////////////////   cout << "\nmax = " << MaxSum(data, id) << endl;  cout << clock() << endl;    getchar();getchar(); return 0;} void Connected(int id[], int p, int q)//把连在一起的花合并到一组{ if (id[p] == id[q]) //已经连通   return; int t = id[p];  for (int i=1; i<=N; i++) {  if (id[i] == t)    id[i] = id[q];  }} int MaxSum(const int data[], int id[])//求每一组中数据之和的最大值{ int buf[N] = {0}; int max = 0; int sum = 0;  for (int k,i=1; i<=N; i++) //遍历数组id， 计算并查找和最大的集合  {  if (id[i] == 0)   continue;    k = 1;   for (int j=i+1; j<=N; j++) //记录以i为根的所有元素的下标   {   if (id[j] != 0 && id[j] == id[i])   {    buf[k++] = j;    id[j] = 0;   }  }  buf[0] = i;  id[i] = 0;    sum = 0;  for (int t=0; t<k; t++) //计算以i为根的集合的和  {   if (data[buf[t]] > 0)    sum += data[buf[t]];  }    if (sum > max)   max = sum; }  return max;}

评论