Systems of difference constraints P23267


Statement
 

pdf   zip

html

A system of difference constraints is a set of inequations of the kind xyk, where x and y are integer variables, and k is an integer constant. Given a system of difference constraints, a solution is an assignment of values to variables in such a way that all inequations hold.

For instance, the system of difference constraints { x1x2 ≤ 4, x2x3 ≤ −1, x3x1 ≤ −2 } has, among other solutions, x1 = 4, x2 = 0 and x3 = 2.

Write a program that, given a system of difference constraints with n variables x1, …, xn and m inequations among them, tells if there is some solution or not.

Input

Input consists of several cases. Every case begins with n and m, followed m triplets i, j, k, with ij, for the inequation xixjk. Assume 1 ≤ n ≤ 103, 0 ≤ m ≤ 5n, −105k ≤ 105, and that every pair of i and j appears at most once. All given numbers are integers.

Output

For every case, print “yes” if the system has some solution, and print “no” otherwise.

Public test cases
  • Input

    3 3
    1 2 4
    2 3 -1
    3 1 -2
    
    3 3
    1 2 3
    2 3 -2
    3 1 -2
    
    4 6
    2 4 -2
    4 2  2
    1 2  1
    1 4  3
    4 3  2
    3 1 -1
    

    Output

    yes
    no
    yes
    
  • Information
    Author
    Enric Rodríguez
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Tretzè Concurs de Programació de la UPC - Final
    Date
    2015-09-16