TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2711
  • Problem
  • P2711【网络流】上下界可行流
    Limits : Time Limit : 6000 MS   Memory Limit : 123456 KB
    Description

    给一个无源无汇的流量网络,每条边容量有上界u,下界d,判断是否有可行流。

    Input Format

    第一行一个整数T,表示有T组测试数据。
    每组数据第一行为两个数N,M,表示有N各节点M条边,
    接下来M行每行四个整数s,t,d,u,表示s到t有一条上界u,下界d的边。

    Output Format

    每组数据输出一行,若有可行流输出"Yes",否则输出"No"。

    Sample Input

    样例输入1
    1
    3 3
    1 2 0 1
    2 3 1 2
    3 1 1 1

    样例输入2:
    2
    4 6
    1 2 2 3
    2 3 2 4
    3 1 8 8
    1 4 1 5
    4 3 5 7
    4 2 1 1
    4 5
    1 2 2 3
    2 3 2 4
    3 1 8 8
    1 4 1 5
    4 3 5 7

    Sample Output

    样例输出1:
    Yes

    样例输出2:
    No
    Yes

    Hint

    1<=T<=5
    1<=N<=300
    1<=M<=10000
    1<=s,t<=N
    0<=d<=u<=1000


    Source  感谢nodgd放题并提供数据