1

Topic: How economically to analyze the graph

Time limit 1. Constructed new school. The school contains N the offices enumerated from 1 to N, between some of them doors. When the pupil transits through a door, it receives a certain amount of knowledge. The input in school is in an office 1, and an output in N. Each pupil transits school exactly once and arrives in certain high school depending on the typed points (at an input in school this point is equal to zero). Your task to show the best result. The input data the First line of an input file contains integer numbers N (1 <= N<=2000) - an amount of offices and M (1<=M<=10000) an amount of doors. In each of following M of lines the door description contains: office number from which and in which they conduct, and also the integer number which defines an amount of knowledge received at passage through a door (this number on the unit does not exceed 10000). Doors can conduct from an office in that office, between two offices can be more than one door. The initial data In the output file deduce "yes" - if it is possible to receive beyond all bounds a large supply of knowledge, "no" - if it is impossible to transit school, and the maximum quantity of knowledge an opposite case. That is clear: 1) oriented graph 2) is set if there are no loops and cycles, the graph - coherent then 1 - a source, N - a sink, and the decision is we received loops or a cycle (check by algorithm bfs or dfs) where the total after arcs is positive - then "yes" 4) if between 1 are algorithm of "finding of the maximum flow" 3) if and N there is no way (algorithm bfs or dfs), then "no". That causes a question: if to apply all these algorithms for "the big" graph preliminary check on acyclicity, connectivity check can occupy a lot of time. On what it is possible (within the limits of a task in view) - to spare?