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[20000];
int edge_v[20000];
int edge_w[20000];
int dist[2000];
int null[2000];

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]	= 0;
		dist[0] = 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)
			fprintf(stdout, "Bad Estimations\n");
		else
		{
			fprintf(stdout, "%d\n", dist[n+1]-dist[1]);
		}
	}
}

Leave a Reply

Your email address will not be published.

+ 12 = 15