1082. 关系运算图

时间限制 1000 ms
内存限制 128 MB

题目描述

给出一有向图,图中每条边都被标上了关系运算符‘< ’,‘> ’,‘=’。现在要给图中每个顶点标上一个大于等于0,小于等于k的某个整数使所有边上的符号得到满足。若存在这样的k,则求最小的k,若任何k都无法满足则输出NO。

例如下表中最小的k为2。

结点1> 结点2
结点2> 结点3
结点2> 结点4
结点3=结点4

如果存在这样的k,输出最小的k值;否则输出‘NO’。

输入数据

共二行,第一行有二个空格隔开的整数 $n$ 和 $m$ 。 $n$ 表示 $G$ 的结点个数 $,m$ 表示 $G$ 的边数,其中 $1\le n\le 1000, 0\le m< 10^{3}$ 。全部结点用 $1$ 到 $n$ 标出,图中任何二点之间最多只有一条边,且不存在自环。
第二行共有 $3m$ 个用空格隔开的整数,第 $3i-2$ 和第 $3i-1\ (1\le i\le m)$ 个数表示第 $i$ 条边的顶点。第 $3i$ 个数表示第 $i$ 条边上的符号,其值用集合 ${-1, 0, 1}$ 中的数表示 $:-1$ 表示‘< ’, 0 表示‘=’, 1表示‘> ’。

输出数据

仅一行,如无解则输出‘NO’;否则输出最小的 $k$ 的值。

样例输入

4 4
1 2 -1 2 3 0 2 4 -1 3 4 -1

样例输出

2

题目信息

未提交
未通过无法查看
未通过无法查看