解题思路:
本题等价于:
有一张有 m 条边的有向图,在图中补上若干条边使得存在一条欧拉路径可以覆盖图中每一条边仅一次。求补边后整张图边数的最小值。
设一个连通块中,每个点入度减去出度的值之和为 t。
若 t>0,则为了让它符合欧拉回路的存在条件,至少再连 t 条边。
若 t=0,为了使图连通,至少连 1 条边。
故答案为
m+∑max(1,t);
注意事项:无
参考代码:无
0.0分
1 人评分
小明A+B (C语言代码)浏览:1247 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:548 |
C语言程序设计教程(第三版)课后习题7.2 (C语言代码)浏览:661 |
简单的for循环浏览:1408 |
【偶数求和】 (C语言代码)浏览:556 |
C语言训练-亲密数 (C语言代码)浏览:682 |
1017题解浏览:583 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:466 |
1012题解浏览:861 |
大家好,我是验题君浏览:576 |