首页 > Defend Your Country
开通博客写题解
头像 Zechariah
发表于 2021-08-03 10:49:35
J. Defend Your Country 前言 思维题，主要是要猜结论证结论。 Solution 对于n是偶数的情况，显然不需要删边。 对于n是奇数的情况，删去非割点显然只用删一个，主要是考虑删掉割点的情况。 假设删除了偶数个割点使得答案最优，由于剩下的联通块必然都是偶数个点（否则继续删奇数联通 展开全文
去ta的博客 赞 (6) 回复(3) 收起
头像 sunrise__sunrise
发表于 2021-08-25 16:38:43
题目大意 你有一张个点条边的无向联通图，现在对于图中的连通分量产生的价值做出如下定义。 如果一个联通分量里面点的个数是偶数那么它的价值就是里面每个点权的和。 如果一个连通分量里面点的个数是奇数那么他的价值就是里面每个点权的和的相反数。 保证每个点的点权。 你现在可以选择一个点把它删去，并且它连的边也 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”