洛谷P1084

一、问题描述：

设计目的：深入理解树。
内容：
H 国有 n 个城市，这 n 个城市用 n-1 条双向道路相互连通构成一棵树，1 号城市是首都，
也是树中的根节点。
H 国的首都爆发了一种危害性极高的传染病。当局为了控制疫情，不让疫情扩散到边境城市（叶子节点所表示的城市），决定动用军队在一些城市建立检查点，使得从首都到边境城市的每一条路径上都至少有一个检查点，边境城市也可以建立检查点。
但特别要注意的是，首都是不能建立检查点的。现在，在 H 国的一些城市中已经驻扎有军队，且一个城市可以驻扎多个军队。一支军队可以在有道路连接的城市间移动，并在除首都以外的任意一个城市建立检查点，且只能在一个城市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的长度（单位：小时）。请问最少需要多少个小时才能控制情。注意：不同的军队可以同时移动。
输入格式
第一行一个整数 n，表示城市个数。
接下来的 n-1 行，每行 3 个整数，u,v,w，每两个整数之间用一个空格隔开，表示从城市 u
到城市 v 有一条长为 w 的道路。数据保证输入的是一棵树，且根节点编号为 1。
接下来一行一个整数 m，表示军队个数。
接下来一行 m 个整数，每两个整数之间用一个空格隔开，分别表示这 m 个军队所驻扎的城市的编号。
输出格式
一个整数，表示控制疫情所需要的最少时间。如果无法控制疫情则输出-1。

二、需求分析：

若一个时间限制满足题意，则所有比它大的时间限制一定都满足题意，因此本题答案具有单调性，可以二分答案求解。接下来的重点就是check函数，如何判断一个时间限制符不符合条件呢？显然，对于所有军队，我们希望它最后停留的节点深度越小越好，这样可以控制最多的路径。因此我们让所有的军队尽量地向上走，若一个军队可以走到根节点，则令其暂时停在根节点的子节点；否则走到时间限制内能够走到的深度最小的节点。这个步骤可以用树上倍增进行优化。

经过这步处理后，我们先找出所有以根节点的子节点为根的子树中，是否有到叶子节点的路径还未被驻扎，并记录下还有路径未被驻扎的这些子树的根节点。对于这些节点，可以证明，若该节点上停留有军队，则剩余时间最小的军队驻扎在该节点一定是最优的。这样处理过这些节点后，把剩下的节点按照到根节点的距离从小到大排序。
最后可能还会有一些军队未确定最后的驻扎节点，把这些军队按照剩余时间从小到大排序，然后和上一步处理出来的这些节点一一进行匹配。这是一个可以证明正确性的贪心策略。若所有未被驻扎的节点都有军队驻扎，则说明当前的时间限制可行；反之则不可行。

三、概要设计：

1、数据结构定义：

int n;//城市个数
int m;//军队个数
int TotalLength = 0;//所有路径的长度之和
int T;//f数组和dist数组第二维下标的最大值
int Depths[MAXSIZE];//每个节点的深度，
int ArmyLoc[MAXSIZE];//分别表示这 m 个军队所驻扎的城市的编号
bool Stayed[MAXSIZE];//有无军队驻扎
int F_Num[MAXSIZE][20];//	存储i节点的第 2^j个祖先的节点编号
int F_length[MAXSIZE][20];//存储i节点到第 2^j个祖先的长度
bool need_dfs[MAXSIZE];//根节点的子节点 是否需要被驻扎
int LeftTime[MAXSIZE];// 处理过后仍闲置的军队,只储存剩余时间,不需要存当前停留的位置
int need_last[MAXSIZE];//仍需要被驻扎的节点只存储节点到根节点的距离，不必存储节点编号
pair<int, int> FreeArmy[MAXSIZE];//第一维存储该军队到达根节点后剩余的时间，第二维存储该军队当前所在的节点编号，存储的是能上升的根节点的闲置节点
queue<int> que;//倍增时用到的队列typedef struct LinkList
{int Data = -999;int Power = -999;LinkList* next = NULL;
}LinkList;
LinkList* CCListHead[MAXSIZE];//邻接表用来存储图

2、模块设计：

程序分为以下几个模块：

• MakeCountryGroup();//构建图
• PreTreatment();//树上倍增预处理
• Check()//检查当前的时间限制是否满足要求
• IS_Controled(int x)//dfs序寻找路径未被驻扎的叶子节点

3、各模块间的调用关系：

四、详细设计

主要算法：
1.读入树的信息并用存储图的方式（邻接表）储存（无向图）：MakeCountryGroup();
其中：CCListHead[i]为头的链表上节点的值表示与i节点有连接的节点编号
由于是无向图，每条边要正反存两次。

 cout << "请输入边的信息\n";for (int i = 1; i < n; i++){int x, y, z;cin >> x >> y >> z;for (Current = CCListHead[x]; Current->Data != -999;) {if (Current->next== NULL)Current->next = new LinkList;else Current = Current->next;}if (Current == NULL)Current = new LinkList;Current->Data = y;Current->Power = z;for (Current = CCListHead[y]; Current->Data != -999;) {if (Current->next == NULL)Current->next = new LinkList;else Current = Current->next;}if (Current == NULL)Current = new LinkList;Current->Data = x;Current->Power = z;TotalLength += z;//统计所有边的长度之和}

2：树上倍增预处理：PreTreatment();
计算出所有节点的第2^i个祖先的编号以及到他的距离
int F_Num[N][20];// 存储i节点的第 2^j个祖先的节点编号
int F_length[N][20];//存储i节点到第 2^j个祖先的长度
计算过程用到以下推导公式;
F_Num[i][j]=f[f[i][j-1]][j-1];
F_length[i][j]=dist[i][j-1]+dist[f[i][j-1]][j-1];
具体过程：建立一个空队列，并将根节点入队，同时存储根节点的深度为一
取出队头，遍历所有与其有连接的边。由于存储的时候是按照无向图存储，因此判定某个点是否是其父节点，对于连接到它父亲节点的边，直接跳过即可。记当前路径的另一端节点为 y，处理出 y的 depth、 F_Num、 F_Num三个数组的值，然后将 y入队。
不断重复第2步，直到队列为空。

bool IS_Controled(int x)//dfs序寻找路径未被驻扎的叶子节点
{bool IsLeaf = 1;//用于判断是否是叶子节点if (Stayed[x])return 1;//遇到已驻扎节点，直接返回1LinkList* Current1 = new LinkList;for (Current1 = CCListHead[x]; Current1->Data != -999;){int y = Current1->Data;if (Depths[y] < Depths[x]) {if (Current1->next == NULL)break;else Current1 = Current1->next;continue;//遇到连接父节点的边时continue}IsLeaf = 0; //只要有一条不是连接着父节点的边，说明不是叶子节点if (!IS_Controled(y))//递归，如果子节点未被控制，返回0 //若某个子节点搜索时遇到路径未被驻扎的叶子节点，直接返回0return 0;if (Current1->next == NULL)break;else Current1 = Current1->next;}if (IsLeaf)//当前节点是叶子节点且未被驻扎return 0;return 1;//叶子节点均被控制，返回1
}

3：二分结果
由于最终的答案一定介于0和所有边的权值之和之间，则取区间【L，R】L=0,R=权值之和，mid=L+R/2，判断疫情在mid时间之内能否控制（具体判断方法后面会给出），如果能则说明时间可以进一步缩短，让L=mid缩小范围继续判断，并记录此时的mid为答案，后续不断刷新答案。如果不能说明给的时间不够，则R=mid进一步判断。直到L不再小于R为止，最终得到的答案即为所求。

int Left = 0, Right = TotalLength, Mid;int Answer = -1;//程序结果while (Left <= Right){Mid = (Left + Right)/2;if (Check(Mid))//当前的时间限制满足题意，则更新答案Right = Mid - 1, Answer = Mid;else //二分扩大时间继续判断Left = Mid + 1;}

下面是检查疫情能否在给定时间得到控制的具体方法，即Check函数的具体实现：

流程图：

4：上移军队并存储闲置军队
将军队上移到根节点的子节点或者能够达到的最浅节点后，若该军队还能向上到达根节点，说明它还有转移到其它子树去驻扎的可能，因此将它记为暂时闲置，用一个二元组存储起来；否则就将该军队驻扎在当前节点，并将当前节点标记为已驻扎。

 for (int i = 1; i <= m; i++){int x = ArmyLoc[i];//第i个军队所在的城市int cnt = 0;//cnt统计时间花费for (int j = T; j >= 0; j--)if (F_Num[x][j] > 1 && cnt + F_length[x][j] <= lim)//若终点在根节点之前且不会超过时限{cnt += F_length[x][j];x = F_Num[x][j];}if (F_Num[x][0] == 1 && cnt + F_length[x][0] <= lim) {//若当前节点为根节点的子节点且该军队可以在时限内到达根节点cnt_h++; //存储的是能上升的根节点的闲置节点FreeArmy[cnt_h].first = lim - cnt - F_length[x][0];//第一维存储该军队到达根节点后剩余的时间，FreeArmy[cnt_h].second = x;//第二维存储该军队当前所在的节点编号}elseStayed[x] = 1;//将该军队驻扎在当前节点，并将当前节点标记为已驻扎。}

5：dfs寻找路径未被驻扎的叶子节点：IS_Controled(int x)
从每个根节点的子节点开始搜索，若搜索时遇到已驻扎节点，则返回1；
若一直搜索到某个叶子（除了与父亲节点相连的边之外没有其他边）节点都没有遇到已驻扎节点，则说明根节点的这个子节点需要军队驻扎，返回0。
如果当前不是叶子节点并且当前节点的子节点均被控制，也返回1。
当遇到连接父节点的边时，continue即可。
dfs序查找结束后，存储根节点的需要被驻扎的子节点。

 for (Current = CCListHead[1]; Current->Data != -999;) {if (!IS_Controled(Current->Data)) //dfs寻找路径未被驻扎的叶子节点need_dfs[Current->Data] = 1;//dfs查找结束后，存储需要根节点的需要被驻扎的子节点。if (Current->next == NULL)break;else Current = Current->next;}

6： 对根节点的需要被驻扎的子节点进行初步处理
对于任意一个需要被驻扎的节点，若它上面停留着一支不能到达根节点并返回该节点的军队，则令其驻扎在该节点；另外的，因为一个节点只需要一支军队驻扎，因此我们在这里选择剩余时间最小的节点。所以在处理前要先将 h数组按照剩余时间从小到大排序。
对于处理过后仍闲置的军队，将它们的剩余时间存储起来，只要存储剩余时间就好。

  sort(FreeArmy + 1, FreeArmy + cnt_h + 1);//军队到达根后剩余时间从小到大排序for (int i = 1; i <= cnt_h; i++){//需要被驻扎的节点，若上面停留着一支军队不能到达根并返回，则令其驻扎在该节点；  if (need_dfs[FreeArmy[i].second] && FreeArmy[i].first < F_length[FreeArmy[i].second][0])need_dfs[FreeArmy[i].second] = 0;//去除标记else //对于处理过后仍闲置的军队，将它们的剩余时间存储起来备用。LeftTime[++LeftArmy] = FreeArmy[i].first;}

7. 找到仍需要被驻扎的节点并存储
   经过第6步的初步处理，可能还有一些节点需要被驻扎，此时遍历一遍根节点的子节点，找到这些节点并存储起来。与第6步相同，这里只要存储节点到根节点的距离就可以了，不必存储节点编号。

 for (Current = CCListHead[1]; Current->Data != -999;) {if (need_dfs[Current->Data])//找到仍需被驻扎的节点并存储need_last[++UnsettledNode] = F_length[Current->Data][0];//值为到根的长度if (Current->next == NULL)break;else Current = Current->next;}

8. 最后的匹配
   这里用到一个贪心策略：对于现在闲置的军队和需要被驻扎的节点，让剩余时间小的军队优先驻扎在距离根节点近的节点，这样可以保证决策最优。匹配过后，若所有需要被驻扎的节点都已有军队驻扎，则说明当前的时限可行；反之则不可行。
   sort(LeftTime + 1, LeftTime + LeftArmy + 1),
   sort(need_last + 1, need_last + UnsettledNode + 1); //分别对军队的剩余时间和节点到根节点的距离进行升序排序

int i = 1, j = 1;
while (i <= UnsettledNode && j <= LeftArmy)//扫描整个tim和ned数组 
{if (LeftTime[j] >= need_last[i])//若可行i++, j++;//都扫描到下一位elsej++;//否则扫描下一支军队
}if (i > UnsettledNode)//说明所有需要被驻扎的节点都已被驻扎return 1;
elsereturn 0;

八、测试结果：

第一组测试数据：

输出结果：3，符合预期

第二组测试数据：

输出结果：9，符合预期