首页 > 试题广场 >

下图所示，A 到 B 是连通的。假设删除一条细的边的代价是

[填空题]
下图所示，A 到 B 是连通的。假设删除一条细的边的代价是 1，删除一条粗的边的代价是 2，要让 A、B 不连通，最小代价是(____1____)（2 分），最小代价的不同方案数是(___2____)（3 分）。（只要有一条删除的边不同，就 是不同的方案）
查看正确选项
添加回答
青韵之星头像 青韵之星
我的想法是作出其对偶图再求最短路的条数（平面图最大流:这我熟啊）
发表于 2022-08-28 18:29:43 回复(0)
Helena_Slytherin头像 Helena_Slytherin

题图
二分图。
我的做法是从终点B开始枚举和B在一个集合里的点并计数。理论上可能有更快的做法。

发表于 2022-07-31 16:54:25 回复(0)
提交观点

问题信息

提高 C++ Pascal 图论 问题求解
来自：NOIP2017初赛提高组
上传者：牛客309901号
难度：
2条回答 4110浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号