当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

3147:John's Canonical Difference Bound Matrices

Special Judge 特殊评判
题目描述

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 A1A2 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.

For simplicity, he let C0 = C ∪ {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 dijZ ∪ {$}, # ∈ {<, ≤}. The value of Dij can be evaluated in the following form:

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

For example, DBM of the clock zone given by x1x2 < 2 ∧ 0 < x2 ≤ 2 ∧ 1 ≤ x1 is shown below:

(0, ≤)(−1, ≤)(0, <)
(4, <)(0, ≤)(2, <)
(2, ≤)(1, <)(0, ≤)

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 x1x2 < 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:

(0, ≤)(−1, ≤)(0, <)
(4, <)(0, ≤)(2, <)
(2, ≤)(1, <)(0, ≤)

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 xixj < d or xixjd (0 ≤ i, jm, −10000 < d < 10000). If r = 0, then this line represents an inequality in the form of xixj < d, otherwise it represents an inequality in the form of xixjd. 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.

输出解释

For each test case, first output “Case #:” on a single line, where # is the case number starting from 1. Print a blank line after each test case.

For each test case, output the description of the canonical difference bound matrix. If it doesn’t have a canonical difference bound matrix, print “Canonical DBM does not exist.” (without quotes); If it has a such canonical difference bound matrix, print the matrix in the format as indicated in the sample output. Every element Dij of the matrix should be written in the form (dij, #), where # is either < or <=. If the bound of xixj for xi and xj is unknown, print ($,<) at the position (i, j). Two consecutive elements on each row should be separated by a single space.

输入样例
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,<=)

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Shanghai 2006

源链接: POJ-3147

最后修改于 2020-10-29T06:54:15+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
2000 65536