#P3345. Pku2914 Minimum Cut全局最小割

Pku2914 Minimum Cut全局最小割

最小割 / Minimum Cut

题目描述

给定一张带权无向图。把顶点分成两个非空集合,割的权值定义为两个端点分处两集合的所有边的权值之和。求所有划分中最小的割权值。

输入格式

从标准输入读取。第一行有两个整数 N,MN,M,分别表示顶点数和边数。顶点编号为 11 到 NN。

接下来 MM 行,每行三个整数 a,b,ca,b,c,表示在不同顶点 a,ba,b 之间有一条权值为正整数 cc 的无向边。同一对顶点至多有一条边。

输出格式

向标准输出写入。输出一行一个整数,表示最小割的权值。若图不连通,答案为 00。

样例 1

3 3
1 2 1
2 3 1
3 1 2
2

数据范围

2≤N≤5002\le N\le500,0≤M≤min⁡{10000,N(N−1)/2}0\le M\le\min\{10000,N(N-1)/2\}。