# System of Difference Constraints and ZOJ 2770 Burn the Linked Camp

A system of difference constraints has n variables and m inequations. Each inequation is like:
`x_i - x_j <= b_k`
where `i, j ∈[1, n]`

Here is an example of a system of difference constraints:
``` x_2 - x_5 <= 1 x_1 - x_2 <= 0 x_1 - x_5 <= -1 x_3 - x_1 <= 5 x_4 - x_1 <= 4 x_4 - x_3 <= -1 x_5 - x_3 <= -3 x_5 - x_4 <= -3 ```

The goal is to find an `X = [x_1, x_2, x_3, x_4, x_5]` which satisfies the above-referenced inequations.

To solve such a problem, we usually convert these inequations to a graph, as in a graph there is:
``` d[v] <= d[u] + w(u, v) ```
where d(v) is the distance between v and a certain node, and w(u, v) is the weight of the edge connecting u and v.
It can be easily transformed into
``` d[v] - d[u] <= w(u, v) ```

For a given inequation
``` x_i - x_j <= b_k ```
we can construct two nodes i and j, and an edge from j to i whose weight is b_k.

we also need to make up a source node so that d[x] represents the distance from source to x. The initial weight from source to any node is usually zero, or an arbitrary number.

After we constructed this graph, solving these ineqations becomes as easy as calculating the shortest path from source to each node. Since weight can be negative value, Bellman-Ford (BF) Algorithm or Shortest Path Faster Algorithm (SPFA) is usually used.

If any of these inequations are conflicting, for example:
``` x_1 - x_2 <= -1 x_2 - x_1 <= -1 ```
Then they will become a negative cycle. Fortunately BF or SPFA algorithm can detect it, so we do know if these inequations have no solution.

Let’s see a real problem, which can be found here.

``` ZOJ Problem Set - 2770 Burn the Linked Camp Time Limit: 2 Seconds Memory Limit: 65536 KB```

``` 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 ```

For the first sample, we are given:
``` x_1 <= 1000 x_2 <= 2000 x_3 <= 1000 x_1 + x_2 >= 1100 x_2 + x_3 >= 1300 ```

And the solution is:
``` x_1 = 0 x_2 = 1100 x_3 = 200 ```
so the output is x_1 + x_2 + x_3 = 1300

To convert this problem into a system of difference constraints problem, we need to define that:
`y_i = x_1 + x+2 + ... + x_i`

Then this sample becomes:
``` y_1 - y_0 <= 1000 y_2 - y_1 <= 2000 y_3 - y_2 <= 1000 y_2 - y_0 >= 1100 then y_0 - y_2 <= -1100 y_3 - y_1 >= 1300 then y_1 - y_3 <= -1300 ```
and we also know these by default:
``` x_1 >= 0 x_2 >= 0 x_3 >= 0 ```
so we have:
``` y_1 - y_0 >= 0 then y_0 - y_1 <= 0 y_2 - y_1 >= 0 then y_1 - y_2 <= 0 y_3 - y_2 >= 0 then y_2 - y_3 <= 0 ```

Then we can easily build a graph to solve this problem.

```//ZOJ 2770
//LANG: C++

#include <stdio.h>
#include <stdlib.h>

int edge_u;
int edge_v;
int edge_w;
int dist;
int null;

int main(int argc, char* argv[])
{
int n, m;
int t1,t2,t3;
int eid;
while(fscanf(stdin, "%d %d", &n, &m)!=EOF)
{
eid = 0;
for(int i=1; i<n+2; i++)
{
edge_u[eid] = 0;
edge_v[eid] = i;
edge_w[eid] = 0;
eid++;
}
for(int i=2; i<n+2; i++)
{
edge_u[eid] = i;
edge_v[eid] = i-1;
edge_w[eid] = 0;
eid++;
}
for(int i=0; i<n; i++)
{
fscanf(stdin, "%d", &t1);
edge_u[eid] = i+1;
edge_v[eid] = i+2;
edge_w[eid] = t1;
eid++;
}

for(int i=0; i<m; i++)
{
fscanf(stdin, "%d %d %d", &t1, &t2, &t3);
edge_u[eid] = t2+1;
edge_v[eid] = t1;
edge_w[eid] = -t3;
eid++;
}

//BF
//init
for(int i=0; i<n+2; i++)
{
null[i] = 1;
}
null	= 0;
dist = 0;

//relax
for(int i=0; i<n+1; i++)
{
for(int j=0; j<eid; j++)
{
int u = edge_u[j];
int v = edge_v[j];
int w = edge_w[j];
if((null[v] == 1 && null[u] == 0))
{
null[v] = 0;
dist[v] = dist[u]+w;
}
else if(null[v]==0 && null[u] == 0)
{
if(dist[v]>dist[u]+w)
{
dist[v] = dist[u]+w;
}
}

}
}

//check negative
int flag = 0;
for(int i=0; i<eid; i++)
{
int u = edge_u[i];
int v = edge_v[i];
int w = edge_w[i];
if((null[v] == 1 && null[u] == 0))
{
flag = 1;
break;
}
else if(null[v]==0 && null[u] == 0)
{
if(dist[v]>dist[u]+w)
{
flag = 1;
break;
}
}
}

if(flag == 1)