经第一轮调整，调整过程终止，即问题无解。
从样例2所给不等式也可看出，因为：
T1-T2≤-3，→T2>T1
T2-T5≤-1，→T5>T2
T5-T1≤-5，→T1>T5
这三个不等式不能同时成立，因此问题无解。
5.3服务器储存信息问题
源程序名servers.?
?
?
（pas,c,cpp）
可执行文件名servers.exe
输入文件名servers.in
输出文件名servers.out
【问题描述】
Byteland王国准备在各服务器间建立大型网络并提供多种服务。
网络由n台服务器组成，用双向的线连接。
两台服务器之间最多只能有一条线直接连接，同时，每台服务器最多只能和10台服务器直接连接，但是任意两台服务器间必然存在一条路径将它们连接在一起。
每条传输线都有一个固定传输的速度。
δ（V,W）表示服务器V和W之间的最短路径长度，且对任意的V有δ（V,V）＝0。
有些服务器比别的服务器提供更多的服务，它们的重要程度要高一些。
我们用r（V）表示服务器V的重要程度（rank）。
rank越高的服务器越重要。
每台服务器都会存储它附近的服务器的信息。
当然，不是所有服务器的信息都存，只有感兴趣的服务器信息才会被存储。
服务器V对服务器W感兴趣是指，不存在服务器U满足，r（U）>r（W）且δ（V,U）<δ（V,W）。
举个例子来说，所有具有最高rank的服务器都会被别的服务器感兴趣。
如果V是一台具有最高rank的服务器，由于δ（V,V）＝0，所以V只对具有最高rank的服务器感兴趣。
我们定义B（V）为V感兴趣的服务器的集合。
我们希望计算所有服务器储存的信息量，即所有服务器的|B（V）|之和。
Byteland王国并不希望存储大量的数据，所以所有服务器存储的数据量（|B（V）|之和）不会超过30n。
你的任务是写一个程序，读入Byteland王国的网络分布，计算所有服务器存储的数据量。
【输入】
第一行两个整数n和m，（1≤n≤30000，1≤m≤5n）。
n表示服务器的数量，m表示传输线的数量。
接下来n行，每行一个整数，第i行的整数为r（i）（1≤r（i）≤10），表示第i台服务器的rank。
接下来m行，每行表示各条传输线的信息，包含三个整数a，b，t（1≤t≤1000，1≤a，b≤n，a≠b）。
a和b是传榆线所连接的两台服务器的编号，t是传输线的长度。
【输出】
一个整数，表示所有服务器存储的数据总量，即|B（V）|之和。
【样例】
servers.inservers.out
439
2
3
1
1
1430
2320
3420
注：
B
（1）={1，2}，B
（2）={2}，B（3）={2，3}，B（4）={1，2，3，4}。
【知识准备】
Dijkstra算法，及其O（（n+e）log2n）或O（nlog2n+e）的实现。
【算法分析】
本题的难点在于问题的规模。
如果问题的规模在100左右，那么这将是一道非常容易的题目。
因为O（n3）的算法是很容易想到的：
（1）求出任意两点间的最短路径，时间复杂度为O（n3）；
（2）枚举任意两点，根据定义判断一个节点是否对另一个节点感兴趣，时间复杂度为O（n3）。
当然，对于30000规模的本题来说，O（n3）的算法是绝对不可行的，即便降到O（n2）也不行，只有O（nlog2n）或O（n）是可以接受的。
既然现在可以得到的算法与要求相去甚远，要想一鼓作气得到一个可行的算法似乎就不是那么容易了。
我们不妨先来看看我们可以做些什么。
判断一个节点V是否对节点W感兴趣，就是要判断是否存在一个rank大于r（W）的节点U，δ（V,U）<δ（V,W）。
所以，节点V到某个特定的rank的节点（集合）的最短距离是一个非常重要的值。
如果我们可以在O（nlog2n）时间内求出所有节点到特定rank的节点（集合）的最短距离，我们就成功地完成了算法的一个重要环节。
用Dijkstva算法反过来求特定rank的节点（集合）到所有点的最短距离——以所有特定rank的节点为起点（rank=1,2,3,…或10），求这一点集到所有点的最短距离。
由于图中与每个点关联的边最多只有10条，所以图中的边数最多为5n。
用PriorityQueue（Heap,WinnerTree或FibonacciHeap等）来实现Dijkstra算法，时间复杂度为O（（n+e）log2n）（用FibonacciHeap实现，更确切的时间复杂度是O（nlog2n+e））。
这里，e＝5n，因而求一遍最短路径的时间复杂度为O（nlog2n）。
由于1≤rank≤10，每个rank都要求一遍最短路径，所以求出每个节点到所有rank的最短路径长度的时间复杂度为O（10*（5+1）nlog2n），即O（nlog2n）。
求出所有点到特定rank的节点（集合）的最短距离，就完成了判断任意节点V对W是否感兴趣的一半工作。
另一半是求任意节点V到W的最短距离。
前面求节点到rank的最短距离时，利用的是rank范围之小——只有10种，以10个rank集合作起点，用Dijkstra算法求10次最短路径。
但是，如果是求任意两点的最短路径，就不可能只求很少次数的最短路径了。
一般来说，求任意两点最短路径是Ω（n2）的（这只是一个很松的下界），这样的规模已经远远超出了可承受的范围。
但是，要判断V对W是否感兴趣，δ（V,W）又是必须求的，所以n次Dijkstra算法求最短路径肯定是逃不掉的（或者也可以用一次Floyd算法代替，但是时间复杂度一样，可认为等价）。
那么，我们又能从哪里来降这个时间复杂度呢？
题目中提到：
所有服务器储存的数据量（|B（V）|之和）不会超过30n。
这就是说，最多只存在30n对（V,W）满足V对W感兴趣。
所以，就本题来说，我们需要处理的点对最少可能只有30n个，求最短距离的下界也就变成Ω（30n）=Ω（n）了（当然，这也只是很松的下界）。
虽说下界是Ω（n），其实我们只需要有O（nlog2n）的算法就可以满足要求了。
从前面估算下界的过程中我们也看到，计算在下界中的代价都是感兴趣的点对（一个节点对另一个节点感兴趣），其余部分为不感兴趣的点对。
我们如果想降低时间复杂度，就要避免不必要的计算，即避免计算不感兴趣的点对的最短路径。
我们来看当V对W不感兴趣时的情况。
根据定义，δ（V,W）>δ（V,r（W）+1）。
如果是以W为起点，用Dijkstra算法求最短路径的话。
当扩展到V时，发现V对W不感兴趣，即δ（V,W）>δ（V,r（W）+1）。
那么，如果再由V扩展求得到U的最短路径，则：
δ（U,W）=δ（V,W）+δ（U,V），
δ（U,r（W）+1）=δ（V,r（W）+1）+δ（U,V），
由于δ（V,W）>δ（V,r（W）+1），
所以δ（V,W）+δ（U,V）>δ（V,r（W）+1）+δ（U,V），即δ（U,W）>δ（U,r（W）+1）
所以，U对W也不感兴趣。
因此，如果以W为起点，求其他点到W的最短路径，以判断其他点是否对W感兴趣，当扩展到对W不感兴趣的节点时，就可以不继续扩展下去了（只扩展对W感兴趣的节点）。
我们知道，所有感兴趣的点对不超过30n。
因此，以所有点作起点，用Dijkstra算法求最短路径的时间复杂度可由平摊分析得为O（30（n+e）log2n）=O（30（n+5n）log2n）=O（nlog2n）。
由此，我们看到判断一节点是否对另一节点感兴趣，两个关键的步骤都可以在O（nlog2n）时间内完成。
当然算法的系数是很大的，不过由于n不大，这个时间复杂度还是完全可以承受的。
下面就总结一下前面得到的算法：
（1）分别以rank=1,2,…,10的节点（集合）作为起点，求该节点（集合）到所有点的最短距离（其实也就是所有点到该节点（集合）的最短距离）；
（2）以每个点作为起点，求该点到所有点的最短距离。
当求得某节点的最短距离的同时根据求得的最短距离和该节点到rank大于起点的节点（集合）的最短距离，判断该节点是否对起点感兴趣。
如果感兴趣，则找到一对感兴趣的点对，否则，停止扩展该节点，因为该节点不可能扩展出对起点感兴趣的节点。
总结解题的过程，可以发现解决本题的关键有三点：
一是稀疏图，正因为图中边比较稀疏所以我们可以用Dijkstra+PriorityQueue的方法将求最短路径的时间复杂度降为O（nlog2n）；二是rank的范围很小，rank的范围只有10，所以我们只用了10次Dijkstra算法就求得了所有点到特定rank的最短距离；三是感兴趣的点对只有很少，由于感兴趣的点对只有30n，我们通过只计算感兴趣点对的最短路径，将求点与点间最短路径的时间复杂度降到了O（nlog2n）。
这三点，只要有一点没有抓住。
本题就不可能得到解决。
5.4间谍网络（AGE）
源程序名age.?
?
?
（pas,c,cpp）
可执行文件名age.exe
输入文件名age.in
输出文件名age.out
【问题描述】
由于外国间谍的大量渗入，国家安全正处于高度的危机之中。
如果A间谍手中掌握着关于B间谍的犯罪证据，则称A可以揭发B。
有些间谍收受贿赂，只要给他们一定数量的美元，他们就愿意交出手中掌握的全部情报。
所以，如果我们能够收买一些间谍的话，我们就可能控制间谍网中的每一分子。
因为一旦我们逮捕了一个间谍，他手中掌握的情报都将归我们所有，这样就有可能逮捕新的间谍，掌握新的情报。
我们的反间谍机关提供了一份资料，色括所有已知的受贿的间谍，以及他们愿意收受的具体数额。
同时我们还知道哪些间谍手中具体掌握了哪些间谍的资料。
假设总共有n个间谍（n不超过3000），每个间谍分别用1到3000的整数来标识。
请根据这份资料，判断我们是否有可能控制全部的间谍，如果可以，求出我们所需要支付的最少资金。
否则，输出不能被控制的一个间谍。
【输入】
输入文件age.in第一行只有一个整数n。
第二行是整数p。
表示愿意被收买的人数，1≤p≤n。
接下来的p行，每行有两个整数，第一个数是一个愿意被收买的间谍的编号，第二个数表示他将会被收买的数额。
这个数额不超过20000。
紧跟着一行只有一个整数r，1≤r≤8000。
然后r行，每行两个正整数，表示数对（A,B），A间谍掌握B间谍的证据。
【输出】
答案输出到age.out。
如果可以控制所有间谍，第一行输出YES，并在第二行输出所需要支付的贿金最小值。
否则输出NO，并在第二行输出不能控制的间谍中，编号最小的间谍编号。
【样例1】
age.inage.out
3YES
2110
110
2100
2
13
23
【样例2】
age.inage.out
4NO
23
1100
4200
2
12
34
【算法分析】
根据题中给出的间谍的相互控制关系，建立有向图。
找出有向图中的所有强连通分量，用每个强连通分量
升级会员 