Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:128 MB

#139. 最大割

统计

题目描述

给出有向图 $G$,请你割掉一些边,使得 $1$ 不能到 $n$,并且割掉的边权值和最大。

输入格式

第一行两个正整数 $n,m$,为点数和边数。

接下来 $m$ 行,每行三个整数 $x,y,z$,表示 $x\to y$ 的边权值为 $z$。$(1\le x,y\le n)$

输出格式

一行一个正整数,为最大割大小。

样例

输入

2 3
1 2 2
1 2 3
1 1 0

输出

5

解释

前两条边都割。

数据范围

第 $1,2$ 组数据:$n,m\le 10$。

第 $3,4$ 组数据:$z>0$。

第 $1\sim 10$ 组数据:$2\le n\le 500$,$1\le m\le 10000$,$|z|\le 10^{15}$。