#P4663. Hack

    ID: 3797 传统题 1000ms 128MiB 尝试: 239 已通过: 67 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索深度优先搜索图论最小割建模Dinic当前弧优化最大流最小割定理CF2300

Hack

Hack

题目描述

通信网络有 nn 个结点和若干有向边。信息从 00 号结点发出,沿有向边一直传到 n−1n-1 号结点。同一个结点或同一条边可以在一次传递过程中多次经过。

你可以预先入侵若干条边。每次信息经过一条被入侵的边时,都会被截获一次。只有所有可能的传递路线都恰好被截获一次,入侵才成功。

入侵一组边的代价为这组边各自代价的总和。求成功方案的最小代价。

输入格式

第一行两个整数 n,mn,m。

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示一条从 uu 到 vv 的有向边,入侵这条边的代价为 ww。

输出格式

输出一行一个整数,表示最小代价。若不存在成功方案,输出 −1-1。

6 7
0 1 5
0 2 5
1 3 1
2 4 1
4 1 1
3 5 5
4 5 5
6

样例解释

可以入侵 0→10\to1 与 2→42\to4 两条边,总代价为 5+1=65+1=6。

数据范围

2≤n≤1002\le n\le100,1≤m≤25001\le m\le2500,0≤u,v<n0\le u,v<n,1≤w≤1091\le w\le10^9。保证至少存在一条从 00 到 n−1n-1 的路线。