首页 > 试题广场 >

二分图染色(弱化版)

[编程题]二分图染色(弱化版)
  • 热度指数：37 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 512M，其他语言1024M
  • 算法知识视频讲解
给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。
计算所有满足条件的染色的方案数，并对10^9+7取模。
(ps：本题数据量与实际比赛中数据量相比，少了一些)

输入描述:
二分图单边的顶点数目n(n ≤ 10^7)


输出描述:
输出一个整数,即所求的答案。
示例1

输入

2

输出

35
算法知识视频讲解
开通博客
头像 Alan233
发表于 2020-04-09 20:39:10
题目链接：二分图染色 Description 给定一个完全二分图，图的左右两边顶点数目相同。每条边我们都要染成红、绿、蓝中的一种。要求满足任意两条红边不共享端点，任意两条蓝边不共享端点。求出所有满足条件的染色方案数，答案对取模。注：表示二分图其中一边的点数目。数据范围 Solution 我们切换思 展开全文
去ta的博客 赞 (9) 回复(2) 收起
头像 塞蒙尘
发表于 2020-04-09 21:58:15
Solution 首先，我们考虑只染红色/蓝色的情况。 假设当前染了条边，那么一定在其中一边选择了个点，这部分的方案数为； 而在另外一边，选择个点的顺序不同会产生不同的方案，这部分的方案数为； 所以，个点的完全二分图只连条红色/蓝色边的方案数为； 总的方案数即为。 那么，染两种颜色的方案数就很明显了 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 ThinkofBlank
发表于 2020-04-10 15:27:23
乍看一下，此题貌似很简单，仔细一想，竟然完全不可做。。。 然后，开始思考怎么搞这道题。。。 首先，我们因为每个边都要染色，所以，我们不妨先给所有边都染上最没影响的颜色——绿色 然后，我们只需考虑，将绿色的边改成红色或者蓝色即可~ 我们来推导一下 如果既有蓝色，又有红色，尝试推导一下，发现情况太多，而 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 19_hanhan
发表于 2020-04-17 11:55:41
题目 题目描述： 给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿色，并使得任意两条红边不共享端点、同时任意两条蓝边也不共享端点。 计算所有满足条件的染色的方案数，并对10^9+7取模。 ( 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 shyyhs
发表于 2020-08-21 22:05:05
邓老师题解写的十分的好.首先把完全二分图转化成一个二维的棋盘,因为完全二分图的连边可以把左边看成横坐标和右边看成纵坐标.如此题目就变成了,棋盘中同一横纵坐标不能存在相同颜色,且绿色根本不影响结果,我们不妨假设棋盘原本都是绿色,然后涂上红蓝两色...orz我们不妨设f[n]是一种颜色满足要求的所有涂法 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 pamhip
发表于 2020-04-16 12:13:29
题意 给一个 个点的完全二分图（即有 条边），每条边可以染红色，蓝色，绿色。一个点不能连出超过一条红色边，也不能连出超过一条蓝色边。问将这些边染色的方案数有多少种，答案对 取模。() 分析 给这题跪了！我还是太菜了。完全二分图可以转化为一个 的矩阵，第 行第 列的点表示左边第 个点和右边 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 wxyww
发表于 2020-04-09 19:32:46
solution 首先单独考虑蓝色和红色的染色方式。 如果只染蓝色（红色）和绿色，我们枚举一个蓝色边的数量x,然后方案数就是。所以总的方案数就是。 然后容斥合并蓝色和红色的方案。枚举蓝色和红色边重复的数量x,那么答案就是。所以最终答案就是 注意到上面求单个的过程是的。预处理f数组的复杂度就是。所以考 展开全文
去ta的博客 赞 (1) 回复(2) 收起
头像 sunrise__sunrise
发表于 2020-04-10 13:47:12
根据楚巨的描述，这个题目有亿点点难…… 题目传送 Solution 根据二分图的解题套路，可以转换为一个n * n的矩阵中去进行处理，又因为题目给了边的特性，我们假设xi，yi填上红色就是xi，yi的边涂成红色（因为绿色的没啥特性，所以可以不管这种颜色），两红边（蓝边类似）不能共享端点，也就 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 精神病科黄主任
发表于 2020-04-17 11:55:08
考虑只有一种颜色，对于选取i个节点每边有f[n]= 种那么两边的话就有ans=f[n]*f[n].这样是有重复的，考虑容斥结果就是 但是这样复杂度需要n^2 这样就是on递推了 #include <bits/stdc++.h> using namespace std; 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 回归梦想
发表于 2020-04-16 17:29:02
精讲 组合、容斥@[TOC]题目传送 题目： 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 524288K，其他语言1048576K64bit IO Format: %lld 题目描述 给定一个完全二分图，图的左右两边的顶点数目相同。我们要给图中的每条边染成红色、蓝色、或者绿 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

C++工程师 golang工程师 2017 组合数学 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 动态规划 测试开发工程师 大数据开发工程师 Java工程师
来自：CodeM 2017美...
难度：
0条回答 3967浏览

热门推荐

通过挑战的用户

相关试题

二分图染色(弱化版)

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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