1419. 关系运算图

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

输出数据

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

样例输入

复制
4 4
1 2 -1 2 3 0 2 4 -1 3 4 -1
 · \n
 · ·  · · · · · ·  · · ·  \n

样例输出

复制
2
 \n

提交

请先 登录

© 2024 FAQs Contact About