编程题

1731:最大流


时间限制: 3000 ms         内存限制: 262144 KB
提交数:124    通过数: 45

【题目描述】

给定一张$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\n1 3\n2 3\n4 1\n5 6\n2 6\n5 1\n6 4\n5 3

【样例输出2】

36

【数据规模及约定】

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

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

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

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

查看答案
赣ICP备20007335号-2