512
差分約束-zoj-2770
Burn the Linked Camp
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個營，它們都在一條線上，從左到右分別標記為1,...,n。第i個營寨的最大士兵容量為Ci。通過一段時間觀察，陸遜可以估計出[i,j]這些營的士兵和的最小值。最後問估計出的所有士兵的最小數。若估算數據與已知最大容量抵觸，則認為估計錯誤。
分析：記v[i]為前i個兵營中的士兵數。
由題目得以下3個約束條件。
1.v[a]-v[a-1]>=0;要確保每個營中人數不為負。
2.對於容量Ci，有v[i]-v[i-1]<=Ci;
3.對於三元組輸入 a b k,有v[b]-v[a-1]>=k。
全部整理成<=類型的不等式，滿足差分約束條件即可。我們要求最大的k，也就是最小的-k,所以最短路解決問題。
最後更新：2017-04-03 08:26:24