It is well known that, in the period of The Three Empires, Liu Bei, the emperor of the Shu Empire, was defeated by Lu Xun, a general of the Wu Empire. The defeat was due to Liu Bei's wrong decision that he divided his large troops into a number of camps, each of which had a group of armies, and located them in a line. This was the so-called "Linked Camps".
Let's go back to that time. Lu Xun had sent many scouts to obtain the information about his enemy. From his scouts, he knew that Liu Bei had divided his troops into n camps, all of which located in a line, labeled by 1..n from left to right. The ith camp had a maximum capacity of Ci soldiers. Furthermore, by observing the activities Liu Bei's troops had been doing those days, Lu Xun could estimate the least total number of soldiers that were lived in from the ith to the jth camp. Finally, Lu Xun must estimate at least how many soldiers did Liu Bei had, so that he could decide how many troops he should send to burn Liu Bei's Linked Camps.
Input:
There are multiple test cases! On the first line of each test case, there are two integers n (0<n<=1,000) and m (0<=m<=10,000). On the second line, there are n integers C1��Cn. Then m lines follow, each line has three integers i, j, k (0<i<=j<=n, 0<=k<2^31), meaning that the total number of soldiers from the ith camp to the jth camp is at least k.
Output:
For each test case, output one integer in a single line: the least number of all soldiers in Liu Bei's army from Lu Xun's observation. However, Lu Xun's estimations given in the input data may be very unprecise. If his estimations cannot be true, output "Bad Estimations" in a single line instead.
Sample Input:
3 2 1000 2000 1000 1 2 1100 2 3 1300 3 1 100 200 300 2 3 600
Sample Output:
1300 Bad Estimations 刚看会了差分约束，来做的这道题目，可惜题目中没有出现形如模板中的N个变量，M个约束关系，首先这里的三个顶点有了三个值，而且是告诉我们第 i 个顶点到第 j 个顶点最少有多少人 这叫情何以堪啊，想了整整一个上午硬是没有弄明白该如何去构造这个图（在已知该题能够在图论的知识基础上解决他），其实在和同学的讨论中有过接近正确思路的想法，但最后还是没能想 到。 其实这题是将所有给定的数据直接化为一种差分关系，不管是前面给定的三个 “ 顶点值 ” 还是后面的 “ 和值 ”，这题需要将和值看作图中一个个顶点，即将 2号营地到3号营地的总人数看 作是从1号营地到3号营地的人数总和 减去 从1号营地到2号营地的人数总和，将三个营地的人数限制同样转化为一组不等式的关系，关键是要出现差分形式。 以第一个例子讲解：设S[i]代表前 i 个营地的总人数， A[i]代表当前营地的人数，显然 S[i]= A[1]+ A[2]+ A[3]+......+A[i]; 下面将列出如何将所给数据转话为差分关系： 1000 S[1]- S[0]<= 1000 && S[1]- S[0]>= 0 2000 S[2]- S[1]<= 2000 && S[2]- S[1]>= 0 1000 S[3]- S[2]<= 1000 && S[3]- S[2]>= 0 1 2 1100 S[2]- S[0]>= 1100 2 3 1300 S[3]- S[1]>= 1300 接下来就是构建一个图了，注意这里要将所有的不等号统一形式，因为后面要去求最短路或者是最长路，所以在不和谐的式子两端乘以一个负号。如果选择使用 “<= ” 来解这个问题话，那么 就是计算最短路径了，因为对于不等式 A- B<= Z 可以将A看作A到某一顶点的最短距离，B看作B到某一顶点的最短距离，Z看作是B到A的边权值，改变一下不等式得 A<= B+ Z;这是单源 最短路的基本性质。如果选择用 “ >= ” 同样的对于不等式 A- B>= Z 可以将A看作A到某一顶点的最长距离，B看作B到某一顶点的最长距离，改变一下不等式 A>= B+ Z;这时单源最长路 的基本性质。 这里引进了S[0], 其实可以算是为整个差分求解提供了一个“参考系”，其没有实质的意义，但是我们在初始化时，将其值赋为了 ‘0’，这就确保了各个营地的人数不会出现负数。 还有一个很重要的性质就是在一个差分系统中若有一个变量（通常为我们所引进的参考变量）为定值，那么通过最短路求得的各个变量是相对该确定量个最大的解，通过最长路求得的的各个变 量是相对该确定量的最小的解。（ 因为变量值的得出是在赋初始值为INF 以及 -INF 的基础上得来的，前者通过逐渐变小最终产生最大值，后者通过逐渐变大产生最小值 ）求出S[N]到S[0]的 差值即为最终的解。 该题另外一个难点就是如何选取这个参考点，由于最后求的是差值，所以最大值，最小值对结果都没有影响，又因为差分约束的图化解法是建立在求得最短路或最长路的基础上，所以必须 找到一个点能够使得各个点到他都能存在最短路，这使得一般情况下在系统内部找到一个点很困难，因为我们无法确定系统内的点到其他点是否都有通路，我们更倾向于自己虚构一个点，然后 再通过这个点来求解，同样我们这个点在形式上应该和所求想对应，（ 指大于小于号一致 ）这样才会使得逻辑上是统一的，说的更直白的话，就是有路，能够更新得到其他的点。就此题而言， 如果是用看了网上有的人是用最短路来求解的，起始点选取的是最后一个点 N， 很奇怪吧，我也是一头雾水啊，后面才弄明白，原来这里N在上面 “&&” 符号后面的不等式中已经和其他所有的 的点建立一个路径，所以选择该点是可行的。 代码如下：
#include#include #include #include #include #define INF 0x7f7f7f7fusing namespace std;struct Node { int pos, dis;}info;int ti[1005], inqu[1005], dis[1005];bool SPFA( int N, vector< Node >vec[] ){ queue< int >q; vector< Node >::iterator it; for( int i= 0; i<= N;++i ) { dis[i]= INF; ti[i]= 0, inqu[i]= 0; } dis[N]= 0; q.push( N ); inqu[N]= 1; while( !q.empty() ) { int pos= q.front(); q.pop(); inqu[pos]= 0; for( it= vec[pos].begin(); it!= vec[pos].end(); ++it ) { if( dis[it->pos]> dis[pos]+ it->dis ) { dis[it->pos]= dis[pos]+ it->dis; if( !inqu[it->pos] ) { q.push( it->pos ); inqu[it->pos]= 1; ti[it->pos]++; if( ti[it->pos]> N ) { return false; } } } } } return true;}int main( ){ int N, M, x, y, z; while( scanf( "%d %d", &N, &M )!= EOF ) { vector< Node >vec[1005]; for( int i= 1; i<= N; ++i ) { scanf( "%d", &z ); info.pos= i, info.dis= z; // 告诉我们 A_i的值，转化为 S_i- S_i-1<= z ==> S_i-1 - S_i>= -z; vec[i- 1].push_back( info ); info.pos= i- 1, info.dis= 0; // 由该边的关系可知每个营地的最少的人数不能为负数 // 由此我们也能知道以N点为起始点是有机会更新所有的点的距离，也即满足以各个点到某一点（N或者系统内任何满足条件的一点）的最短路来求解这个差分约束系统 vec[i].push_back( info ); } for( int i= 1; i<= M; ++i ) { scanf( "%d %d %d", &x, &y, &z ); info.pos= x- 1, info.dis= -z; vec[y].push_back( info ); } if( SPFA( N, vec ) ) { printf( "%d\n", dis[N]- dis[0] ); } else { puts( "Bad Estimations" ); } for( int i= 1; i<= N; ++i ) { printf( "%d\n", dis[i] ); } } return 0;}