TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P2715
  • 题目
  • P2715【网络流】网络流题目不卡dinic和isap是约定俗成的规矩
    限制 : 时间限制 : 10000 MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    这是一道模板题。

    给定 \(n\) 个点,\(m\) 条边,给定每条边的容量,求从点 \(s\) 到点 \(t\) 的最大流。

    输入格式

    第一行四个整数 \(n , m , s , t\)
    接下来的 \(m\) 行,每行三个整数 \(u , v , c\),表示 \(u\)\(v\),流量为 \(c\) 的一条边。

    输出格式

    输出点 \(s\) 到点 \(t\) 的最大流。

    样例输入

    7 14 1 7
    1 2 5
    1 3 6
    1 4 5
    2 3 2
    2 5 3
    3 2 2
    3 4 3
    3 5 3
    3 6 7
    4 6 5
    5 6 1
    6 5 1
    5 7 8
    6 7 7

    样例输出

    14

    提示

    \(1 \leqslant n \leqslant 100, 1 \leqslant m \leqslant 5000, 0 \leqslant c \leqslant 2 ^ {31} - 1\)