#P3345. Pku2914 Minimum Cut全局最小割
Pku2914 Minimum Cut全局最小割
最小割 / Minimum Cut
题目描述
给定一张带权无向图。把顶点分成两个非空集合,割的权值定义为两个端点分处两集合的所有边的权值之和。求所有划分中最小的割权值。
输入格式
从标准输入读取。第一行有两个整数 ,分别表示顶点数和边数。顶点编号为 到 。
接下来 行,每行三个整数 ,表示在不同顶点 之间有一条权值为正整数 的无向边。同一对顶点至多有一条边。
输出格式
向标准输出写入。输出一行一个整数,表示最小割的权值。若图不连通,答案为 。
样例 1
3 3
1 2 1
2 3 1
3 1 2
2
数据范围
,。