首页 > Color Graph
开通博客写题解
头像 精神病科黄主任
发表于 2020-05-01 14:49:54
K.Color Graph 题意：给了n个点和m条无向边，让你删掉一些边，让剩余的边不存在自环和奇数环，求剩余的边的最大值。 思路：这个考了一个二分图的性质，很遗憾当时确实不知道这个。就是说 如果一个图不存在奇数环，那么一定是一个二分图那么问题就转化为，选择尽可能多的边使得该图是二分图那么我们对这n 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 这次会中奖的！！！
发表于 2020-12-07 20:20:04
K.Color Graph 题意： 给一个无向图n个点m条边，给一些边涂红色。要求红色边不能有奇环.求能染红的最多的边。 解题： 题目中讲到了奇环， 这很容易往二分图上想。 定理：一个无向图是二分图，当且仅当图中不存在奇环 接下里就是找是二分图的最多的边。我们一般是分两个集合进行操作，在这个题中由 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”