题目链接 题意：题解： /*
Author : zzugzx
Lang : C++
Blog : blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define
展开全文
题意：给与一个二分图，给边染色，连接同一端点的边的颜色不能相同，求最少用多少种颜色才能完成染色？ 思路：二分图最大匹配的匈牙利算法，对一条边进行染色，设一个端点最小可染的颜色为x，另一个端点最小可染的颜色为x.①x==y,该边染成x.②x<y,将该边强行染成x，最小可染颜色为y的点显然已经有了
展开全文
根据题意，一个点延伸的所有边，一定是颜色不一样的，求最小颜色数和方案。由于是二分图，最小颜色很显然是全部点的最大度数，关键就在于如何求解方案？我们这样思考，由于存在最小颜色数是最大度数这一结论，所以，我们每次使用一个颜色后，所有度数最大的点的度数肯定会减一，不然就会得出一个错误的构造方案（与结论相反
展开全文
题目描述 给一个没有重边的二分图, 要求给边染色. 有公共点的边不能同色. 问最少用多少种颜色, 并任意构造一组方案. 输入描述: 第一行两个数n和m表示图的点数和边数(0<n<1001,0<m<2001).之后m行每行2个数表示一条边的两个端点. 点从1编号到n.保
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
