• [F] Flow Problem

  • 时间限制: 5000 ms 内存限制: 32768 K
  • 问题描述
  • Network flow is a well-known difficult problem for ACMers. Given a graph, your task is to find out the maximum flow for the weighted directed graph.
  • 输入
  • The first line of input contains an integer T, denoting the number of test cases.
    For each test case, the first line contains two integers N and M, denoting the number of vertexes and edges in the graph. (2 <= N <= 15, 0 <= M <= 1000)
    Next M lines, each line contains three integers X, Y and C, there is an edge from X to Y and the capacity of it is C. (1 <= X, Y <= N, 1 <= C <= 1000)
  • 输出
  • For each test cases, you should output the maximum flow from source 1 to sink N.
  • 样例输入
  • 2
    3 2
    1 2 1
    2 3 1
    3 3
    1 2 1
    2 3 1
    1 3 1
    
  • 样例输出
  • Case 1: 1
    Case 2: 2
    
  • 提示
  • 来源
  • HyperHexagon’s Summer Day Gift
  • 操作

显示春菜