← 返回题目
题库练习 Flow Optimality
← 上一题 下一题 →

A9652 | Flow Optimality

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

Input will begin with two integers $n$ and $m$ ( $2<=n<=200000$ ; $0<=m<=200000$ ), the number of nodes and number of known links in the network, respectively. Following this are $m$ lines with four integers each: $f$ , $t$ , $w$ , $b$ ( $1<=f<=n; 1<=t<=n; f≠t; 1<=w<=100; 0<=b<=100$ ). This indicates there is a link between nodes $f$ and $t$ with weight $w$ and carrying $b$ bandwidth. The direction of bandwidth is from $f$ to $t$ .

输入格式

If the intern's solution is definitely not optimal, print "BAD $x$ ", where $x$ is the first link in the input that violates the optimality of the solution. If the intern's solution may be optimal, print the efficiency of the solution if it can be determined rounded to the nearest integer, otherwise print "UNKNOWN".

输出格式

Although the known weights and bandwidths happen to always be integers, the weights and bandwidths of the remaining links are not restricted to integers.

输入输出样例

输入 #1
4 5
1 2 1 2
1 3 4 1
2 3 2 1
2 4 4 1
3 4 1 2
输出 #1
6
输入 #2
5 5
2 3 1 1
3 4 1 1
4 2 1 1
1 5 1 1
1 5 100 100
输出 #2
BAD 3
输入 #3
6 4
1 3 31 41
1 5 59 26
2 6 53 58
4 6 97 93
输出 #3
UNKNOWN
输入 #4
7 5
1 7 2 1
2 3 1 1
4 5 1 0
6 1 10 0
1 3 1 1
输出 #4
BAD 4
C++ 编辑器
输入
输出