最新消息:380元/半年,推荐全网最具性价比的一站式编程学习平台码丁实验室

信息学奥赛题库- 最大流

C++ 少儿编程 1063浏览 0评论

友情提示:380元/半年,儿童学编程,就上码丁实验室

【题目描述】

给定一张$n$个点、$m$条边的无向图,点从$1$开始编号,保证所有点的度数都不超过$3$。

现在假定每条边的容量都为$1$,请你求出任意两点间的最大流,最后只要输出所有点对($i,j$)($i < j$)间最大流的和。

【输入】

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

接下来$m$行每行两个整数$x、y$,表示$x、y$有边相连。保证图中无重边无自环。

【输出】

输出一行一个整数表示答案。

【输入样例】

4 2
1 2
3 4

【输出样例】

2

【提示】

【样例输入2】

6 8
1 3
2 3
4 1
5 6
2 6
5 1
6 4
5 3

【样例输出2】

36

【数据规模及约定】

对于30%的数据,满足$n,m≤50$。

对于另外10%的数据,满足所有点的度数不超过$2$。

对于另外30%的数据,满足度数为$3$的个数不超过$5$。

对于100%的数据,满足$2≤n≤3000,0≤m≤lfloor frac{3n}{2}rfloor$ 。

您必须 登录 才能发表评论!