SP4110 FASTFLOW - Fast Maximum Flow

    • 2通过
    • 2提交
  • 题目来源 SPOJ 4110
  • 评测方式 RemoteJudge
  • 标签
  • 难度 尚无评定
  • 时空限制 2766ms / 1536MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题意

    给一张n个点m条边的无向图($2 \leq n \leq 5000$ ,$1 \leq m \leq 30000$ ),请计算从1号点到n号点的最大流/最小割。

    输入

    第一行包含两个整数n、m。

    接下来m行每行三个正整数a、b、c,表示在a、b两点间有一条容量为c的边。($1 \leq a,b \leq n$ ,$1 \leq c \leq 10^9$ )

    请注意图中有可能有重边和自环。

    输出

    输出一个整数表示1号点到n号点的最大流/最小割。(请注意这个数不一定能用32位整数,即C++的int或pascal的longint存下)

    Translated by @fjzzq2002

    题目描述

    Given a graph with N (2 ≤ N ≤ 5,000) vertices numbered 1 to N and M (1 ≤ M ≤ 30,000) undirected, weighted edges, compute the maximum flow / minimum cut from vertex 1 to vertex N.

    输入输出格式

    输入格式:

    The first line contains the two integers N and M. The next M lines each contain three integers A, B, and C, denoting that there is an edge of capacity C (1 ≤ C ≤ 10 $ ^{9} $ ) between nodes A and B (1 ≤ A, B ≤ N). Note that it is possible for there to be duplicate edges, as well as an edge from a node to itself.

    输出格式:

    Print a single integer (which may not fit into a 32-bit integer) denoting the maximum flow / minimum cut between 1 and N.

    输入输出样例

    输入样例#1: 复制
    4 6
    1 2 3
    2 3 4
    3 1 2
    2 2 5
    3 4 3
    4 3 3
    输出样例#1: 复制
    5
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。