1. 1.某新建小区要修建多个公共设施，供小区内的居民使用，要求任意2个公共设施之间都要可以互通，可以直接铺一条小路，也可以不直接连通，只要能间接通过小路可达即可。现得到小区物业修路费用统计表，表中列出了任意两公共设施间修建小路的费用，以及该小路是否已经修通的状态。具体要求如下：
1. 公共设施数目N（1< N < 20）；
2. 两个相同公共设施间费用为0；
3. 状态为“已经修通”的公共设施间小路成本为0；

现请设计算法，并编写程序计算出实现目标需要的最低成本，并输出结果。
测试数据文件说明：
测试输入文件命名为“T1_input.in”，每一个测试输入文件包含一个测试用例。每个测试用例的第1行给出公共设施的数目N ( 1< N < 20 )；随后的 N(N-1)/2 行对应公共设施间修建小路的费用及修建状态，每行给4个正整数，数值之间以空格分开，前两个数值代表两个公共设施的编号（从1编号到N），以及修建状态：1表示已建，0表示未建，依次是两公共设施间小路的修建费用。
样例：
输入文件：
3
2 1 0 1
3 1 0 2
3 2 0 4
输出：
最低成本：***
（1）请根据以上要求设计最佳算法，并加以文字说明；
（2）编程实现算法，并以样例文件进行测试，输出结果；
（3）按照下面给定的三个测试数据进行测试，并输出结果。
测试数据一：
4
1 2 0 6
1 3 0 3
1 4 1 8
2 3 0 5
2 4 0 3
3 4 0 4
测试数据二：
5
1 2 0 3
1 3 0 2
1 4 0 4
1 5 1 1
2 3 0 2
2 4 0 3
2 5 0 1
3 4 1 5
3 5 0 4
4 5 0 2
测试数据三：
6
1 2 0 4
1 3 0 2
1 4 0 5
1 5 1 7
1 6 0 3
2 3 0 2
2 4 0 6
2 5 1 2
2 6 0 1
3 4 1 5
3 5 0 4
3 6 0 5
4 5 1 2
4 6 0 3
5 6 0 1
（本题60分，要求1占20分，要求2占10分，要求3占30分）

2、某军事基地的卫星测控站，需要实时采集卫星的数据并进行测控，测控站要求站内工作人员，每天要24小时不间断测控，由于测控站内需要每天都有部分人员值班，所以每天安排值班人员是一件很重要的事情，不同时间段对值班人员数也有要求，具体要求如下表所示：

每班值班的工作人员分别在6,10,14,18,22,2时开始上班，连续工作8小时。测控站站长需要确定每个班次应派多少人员值班，才能既满足要求又使每天上班的人数最少。
（1）请根据以上要求设计最佳算法，并加以文字说明；
（2）编程实现算法，并输出每天上班的最少人数；
（3）按照下面给定的新的排班要求运行算法，并输出每天上班的最少人数。

（本题60分，要求1占20分，要求2占20分，要求3占20分）