Little Wish~ lyrical step~

Question

Problem Description
N children are living in a tree with exactly N nodes, on each node there lies either a boy or a girl.
A girl is said to be protected, if the distance between the girl and her nearest boy is no more than D.
You want to do something good, so that each girl on the tree will be protected. On each step, you can choose two nodes, and swap the children living on them.
What is the minimum number of steps you have to take to fulfill your wish?

Input
The first line has a number T (T <= 150) , indicating the number of test cases.
In a case, the first line contain two number n (1 <= n <= 50), D (1 <= D <= 10000000), Which means the number of the node and the distance between the girls and boys.
The next lines contains n number. The ith number means the ith node contains a girl or a boy. (0 means girl 1 means boy), The follow n - 1 lines contains a, b, w, means a edge connect ath node and bth node, and the length of the edge is w (1 <= w <= 10000000).

Output
For every case, you should output "Case #t: " at first, without quotes. The t is the case number starting from 1.
Then follows the answer, -1 meas you can't comlete it, and others means the minimum number of the times.

Sample Input
1
3 1
0 0 1
1 2 1
1 3 1

Sample Output
Case #1: 1

Answer 1

可也分把这个问题分成两个过程：

  第一个过程先遍历case，对每个case运用第二个过程计算最小步数，然后输出结果；
    第二个过程主要用来解决每个具体case；

下面我主要讲来一下实现这个算法的思路：

    1）根据输入的信息建立两个矩阵和一个常量d，一个矩阵可以描述每个n个节点中对应节点的性别信息，另一个描述任意两节点的距离信息；

      就上面的输入而言，可以建立如下两个矩阵：

                    | 0  0  0 |            | 0  1  1 |
            G =  | 0  0  1 |      D = | 1  0  0 |
                    | 0  0  0 |            | 1  0  0 |

        矩阵G中每个元素值 G(m,n) 为 1 表示：树中m节点和n节点性别不同，并且 m-n = -1 (否则为0），矩阵D中每个元素 D(m,n) 表示m节点和
        n节点的距离。

        显然：对树交换m和n节点的性别会改变G矩阵（记作G'） ；
        交换性别不会改变边的距离，即不会改变D矩阵。

        对D矩阵做一次改变，对任何D(m,n)<=d的元素，令D(m,n) = 0 ，得到的新矩阵记作D'。

        现在这个问题就可以这样来描述，最少经过多少步交换可以让G'×D'=零矩阵（×是对应元素的相乘）

        2）现在假设G是个N维矩阵，考察交换m和m+1节点的性别会对G产生什么样的改变(1<=m<N).
        交换性别的两个节点显然应该满足G(m,m+1)=1，否则说明m和m+1节点性别相同，交换也不会对矩阵 产生任何改变；既然m和m+1节点性别
        不同，那么交换之后，G(m-1,m),G(m+1,m+2)的值要改变：

        形象地表示在下面这个矩阵中

        | 0                                                                        |
        |      0                                                                   |
        |            0                                                             |
        |                  0                                                       |
        |                         0   (m-1,m)                                  |
        |                              (m,m)   (m,m+1)                      |
        |                                         (m+1,m+1) (m+1,m+2) |
        |                                                           0              |
        |                                                                  0       |
      |                                                                        0 |

        可以看出，无论如何交换m节点和m+1节点的性别，也只能影响到主对角线之上那条长为N-1的斜对角线上的值，而上面的N-2维斜三角阵的值
        无法通过交换节点性别而改变。

        3)最后这个算法的构造应该说是很清楚了，在完成第一阶段的输入后，把G矩阵的N-2维斜三角阵和修改过的D矩阵的N-2维斜三角阵的对应元素
        进行比较如果发现有对应元素都不为0，则无论如何交换节点都无法满足问题的要求，输出-1；否则，再做进一步的检查，把上面G矩阵和D'矩阵
  的主对角线之上的N-1长的对角线上的元素分别保存在A数组和B数组中，再做进一步的比较。

  4)A数组是一个有0和1组成的N-1个元素的数组，对于B数组我们只关心其中不为0的元素的索引，把B数组中不为0的元素的索引保存在C数组中。

        A数组中交换两个节点的过程很简单，如果A[m]=1 ，那么改变A[m-1]和A[m+1]的值，0变为1或1变为0。之后就可以和用C对交换后的A矩阵
        检查，看看是否C中索引对应的A的元素都为0：

            for(i=0;i < C.length;i++)
                    {
                            if(!A[C[i]]) return FALSE;
                        }

                        当然，对于比较复杂的情况可能在只进行一次交换后仍达不到题目的要求，这个时候需要若干步才能达到要求，然后找出最小步数。
                        具体的算法我就写了，应该不是特别难想吧