删边只会让连通块变多或不变,因此:
2 块,答案 -1;2 块:不能再删掉连接同一连通块内部、会破坏连通性的桥接生成树边,只能删掉各连通块内部的非树边。最大收益等于总边权减去两个连通块各自最小生成树的边权和;1 块:先求整张图的最小生成树,再额外删掉树上的一条边把树拆成两块。为了收益最大,应删树上权最大的那条边。即答案 = 总边权 − MST 边权和 + MST 最大边权。用 Kruskal 一次完成:按边权升序加边,能连通则加入 MST(从总边权中减去该边,并记录 MST 最大边),同时统计最终连通块数。
给定一张 n 个点、m 条边的无向带权图。每删除一条边可以获得该边的边权。目标是删除若干条边后,图中恰好剩下 2 个连通块,并使获得的边权之和最大。
若初始连通块数量已经不少于 3,则无法通过删边使连通块恰好为 2(删边只会增加连通块数量),此时输出 -1。
约束条件:
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册