北邮数据结构（图的着色问题）

问题：田径会比赛安排问题

设某个田径运动会共有七个项目的比赛，分别为100米、200米、跳高、跳远、铅球、铁饼和标枪。每个选手最多参加3个项目，现有六名选手参赛，他们选择的项目如表1-1所示。考虑到每个选手的参加的各个项目不能同时进行，则如何设计合理的比赛日程，使运动会在尽可能短的时间内完成？

测试数据：

分析：

数据预处理

首先将图中的数据用map矩阵表示出来，为着色算法做基础

具体思想见视频图着色问题（教务处怎么安排考试？）_哔哩哔哩_bilibili，讲的很清楚

着色算法

用vectro处理结点和颜色

代码如下：

#include
#include
#include
using	namespace	std;

//将这7个项目编号，100米（0）、200米（1）、跳高（2）、跳远（3）、铅球（4）、铁饼（5），标枪（6） 
int	map[]=
{
	0,1,0,1,0,1,0,
	1,0,0,0,0,1,0,
	0,0,0,1,1,0,0,
	1,0,1,0,0,0,1,
	0,0,1,0,0,1,1,
	1,1,0,0,1,0,1,
	0,0,0,1,1,1,0	
}; //地图数组，存储的是各个项目之间的关系，如果两个项目不能同时举办，则标记为1 
struct	NODE
{
	int	index;//节点在map中对应的位置
	int	degree;//结点的度
	int	mark;//结点的标记 
};
bool	cmp(NODE	a,NODE	b)
{
	return	a.degree>b.degree;
}//按度数降序排列
int	fillcolor(int	map[],int	n);

int	main()
{
	int	n=fillcolor(map,7);
	cout<<"最少需要安排"<mark;//颜色号集合 
	vectornode;//图中结点集合 
	node.resize(n);
	
	for(int	i=0;i