首页 > ACM题库 > HDU-杭电 > HDU 3305-John’s Canonical Difference Bound Matrices-待解决[解题报告]HOJ
2014
03-16

HDU 3305-John’s Canonical Difference Bound Matrices-待解决[解题报告]HOJ

John’s Canonical Difference Bound Matrices

问题描述 :

When John studied the timed automaton, he met the problem about how to trigger the machine. With the problem deeply studied, he found that it can be ascribed to the clock constraints of the timed automaton. The timed automation in question is described below:

The clock variables, or simply clocks, are variables whose values are integers. Of course, time passes at the same rate for all clocks, and any clock can be reset to zero. John uses C to denote the finite set of clocks, and defines the clock constraints for C as follows:

(1)
All inequalities of the form t#c or c#t are clock constraints, where t is a clock, # is either < or <= , and c is an integer.
(2)
If A1 and A2 are clock constraints, then A1 ^ A2 is a clock constraint.

John notes that a clock constraint can define several regions in some multidimensional space. He wants to know such regions, so he defines the clock zones recursively as follows.

Interesting Yang Yui Triangle
For simplicity, he let C0 = C Interesting Yang Yui Triangle {x0} , where x0 is a reference clock whose value is always 0. The clock zone A can be described by a Difference Bound Matrix D (called a DBM) which is a matrix (Dij) of size | C0|×| C0| . Each Dij has the form (dij,#) , where dij Interesting Yang Yui Triangle ZInteresting Yang Yui Triangle {$} , # Interesting Yang Yui Triangle { < ,<=} . The value of Dij can be evaluated in the following form:

For every inequality xi – xj#dij in clock zone A , let Dij = (dij,#) , where xi and xj are two clocks. If the bound of xi – xj for xi and xj is unknown, let Dij = ($, < ) .

For example, DBM of the clock zone given by x1 – x2 < 2 ^ 0 < x2<=2 ^ 1<=x1 is shown below:

Interesting Yang Yui Triangle
The representation of a clock zone by a DBM is not unique. In this example, there are some implied constraints that are not reflected in the DBM. Since x1 – x2 < 2 and x2<=2 , it must be the case x1 < 4 . Since x0 = 0 , the original D10 = ($, < ) can be changed into D10 = (4, < ) . Such adjusting operation is called the tighten operation.

Now John wants to do the similar adjusting operations of difference bounds for all clocks xi and xj until further application of this tighten operation does not change the matrix. John obtains the following new canonical difference bound matrix:

Interesting Yang Yui Triangle
Note that some clock zone may contain contrary conditions and has not canonical difference bound matrix.

But John can not obtain a canonical difference bound matrix for a complex clock zone. He asks for your help.

输入:

The first line of the input file is a single integer T (1<=T<=20) , which is the number of test cases you must process, followed by T test cases:Each test case consists of several lines. Four integers i , j , d and r are given on each line, representing a constraint xi – xj < d or xi – xj<=d (0<=i, j<=m, -10000 < d < 10000) . If r = 0 , then this line represents an inequality in the form of xi – xj < d , otherwise it represents an inequality in the form of xi – xj<=d . The maximal index m of clocks indicates that the indexes of the clocks are 0, 1,…, m,(1<=m<=100) . Note that you have to get the value of m by yourself.

A symbol # given on a single line indicates the end of a test case.

输出:

The first line of the input file is a single integer T (1<=T<=20) , which is the number of test cases you must process, followed by T test cases:Each test case consists of several lines. Four integers i , j , d and r are given on each line, representing a constraint xi – xj < d or xi – xj<=d (0<=i, j<=m, -10000 < d < 10000) . If r = 0 , then this line represents an inequality in the form of xi – xj < d , otherwise it represents an inequality in the form of xi – xj<=d . The maximal index m of clocks indicates that the indexes of the clocks are 0, 1,…, m,(1<=m<=100) . Note that you have to get the value of m by yourself.

A symbol # given on a single line indicates the end of a test case.

样例输入:

1 
1 2 2 0 
0 2 0 0 
2 0 2 1 
0 1 -1 1
#

样例输出:

Case 1: 
(0,<=) (-1,<=) (0,<) 
(4,<) (0,<=) (2,<) 
(2,<=) (1,<=) (0,<=)

 


  1. 网站做得很好看,内容也多,全。前段时间在博客园里看到有人说:网页的好坏看字体。觉得微软雅黑的字体很好看,然后现在这个网站也用的这个字体!nice!

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。