#include
/* iostream库提供了C++程序中用于处理标准输入/输出流的基本功能 */
#include
/* vector是一种顺序容器，类似于数组，但可以动态扩展。它在末尾插入和删除元素速度快，而在中间插入和删除元素速度较慢。 */
#include
/* algorithm库提供了大量用于操作序列（例如数组、向量、列表等容器）的通用算法，包括查找、排序、复制、移动、修改等操作。 */
#include
/* fstream库提供了用于处理文件输入/输出的类。 /
#include <string.h>
/ string.h头文件包含了C风格字符串处理函数。 */
#include <stdio.h>
/* stdio.h是标准输入/输出头文件，包含了输入和输出函数，例如printf()和scanf()。 */
#include <windows.h>
/* windows.h是编写Windows程序需要的重要头文件，包含了Windows API函数和数据结构的声明。 */
using namespace std;
/* 命名空间std包含了C++标准库的定义。使用using namespace std;可以避免在使用标准库中的元素时重复使用std::前缀。 */
int map[49] = { 0 };
// 根据用户输入的项目编号构建邻接矩阵
void Create(int a[]) {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if ((a[i] != a[j]) && (a[i] != 0) && (a[j] != 0)) {
map[(a[i] - 1) * 7 + (a[j] - 1)] = 1;
}
}
// 图节点结构体
struct Node {
int index; // 节点在矩阵中的行数，即位置
int degree; // 节点度数，用于根据从大到小的度数关系进行着色
int mark; // 节点着色标记
};
string name[] = { '标枪', '铅球', '铁饼', '100m', '200m', '跳远', '跳高' };
// 自定义排序规则：节点度数降序排序
bool cmp(Node a, Node b) {
return a.degree > b.degree;
}
// 创建可视化图表
void Print(vector mark, int n, vector node, int Mark) {
int a[10] = { 0 }; // 存储每个标记对应的项目数
int b = 0, c = 1;
// 计算每个标记对应的项目数
for (int j = 0; j < mark.size(); j++) {
for (int i = 0; i < n; i++)
if (node[i].mark == mark[j])
a[j]++;
}
// 确定项目日程表中列数的最大值
int max = a[0];
for (int j = 0; j < mark.size() - 1; j++) {
if (a[j + 1] > max)
max = a[j + 1];
}
cout << ' _________________________________' << endl; // 打印表格的上边界
// 打印表格内容
for (int p = 0; p < Mark; p++) {
cout << ' | | | | |' << endl; // 打印每一行的内容
if (c == 1)
cout << '|' << ' '; // 打印每一行的左边界
else if (c == 2)
cout << '|' << ' ';
else if (c == 3)
cout << '|' << ' ';
else if (c == 4)
cout << '|' << ' ';
else if (c == 5)
cout << '|' << ' ';
// 打印每一行中每个项目的名称
for (int i = 0; i < n; i++) {
if (node[i].mark == c) {
cout << name[node[i].index] << ' |';
b++;
}
}
// 如果某一行的项目数小于最大值，则用空格补齐
if (b < max)
for (int i = 0; i < max - b; i++)
cout << ' |';
b = 0;
c++;
cout << endl; // 打印每一行的下边界
cout << ' ------------------' << endl;
}
}
// 图着色算法实现
int fillcolor(int map[], int n) {
cout << '邻接矩阵' << endl;
int Mark = 0; // 初始化着色标记
vector mark; // 动态标记集
vector node; // 动态节点集
node.resize(n); // 为节点集分配空间
// 统计图中每个节点的度数
for (int i = 0; i < n; i++) {
node[i].degree = node[i].mark = 0; // 度数、标记均初始化为0
node[i].index = i;
for (int j = 0; j < n; j++) {
if (map[i * n + j] == 1)
node[i].degree++;
}
}
sort(node.begin(), node.end(), cmp); // 将图节点按度数降序排列
// 为每个节点着色
for (int i = 0; i < n; i++) {
// 尝试使用已有的颜色为当前节点着色
for (int j = 0; j < mark.size(); j++) {
if (node[i].mark == 0)
node[i].mark = mark[j];
// 检查是否与相邻节点颜色冲突
for (int k = 0; k < n; k++) {
if ((map[node[i].index * n + k] == 1) && (node[k].mark == node[i].mark)) {
// 发生颜色冲突，取消着色
node[i].mark = 0;
break;
}
}
}
// 如果无法使用已有颜色着色，则使用新的颜色
if (node[i].mark == 0) {
mark.push_back(++Mark);
node[i].mark = mark.back();
}
}
Print(mark, n, node, Mark); // 创建可视化图表
return Mark; // 返回所需比赛场次
};
int main() {
cout << '各项目对应编号为：标枪(1),铅球(2),铁饼(3),100m(4),200m(5),跳远(6),跳高(7) ' << endl;
cout << '请依次将选手所报项目编号输入' << endl;
int a[3] = { 0 };
string b[5] = { '张三', '李四', '王五', '赵六', '李七' };
// 获取每个选手报名参加的项目
for (int i = 0; i < 5; i++) {
cout << '请输入 ' << b[i] << ' 所报项目编号：';
for (int j = 0; j < 3; j++) {
a[j] = cin.get() - 48;
if (j == 2 && a[j] != -38)
cin.get();
else if (a[j] == -38) {
a[j] = 0;
break;
}
}
Create(a); // 根据用户输入构建邻接矩阵
}
// 打印邻接矩阵
for (int i = 0; i < 7; i++) {
for (int j = 0; j < 7; j++)
cout << map[i * 7 + j] << ' ';
cout << endl;
}
int n = fillcolor(map, 7); // 进行图着色并获取所需比赛场次
cout << '将需要比赛' << n << '场' << endl;
system('pause');
}
/*
一句操作数据项的语句是map[(a[i] - 1) * 7 + (a[j] - 1)] = 1;，
它的功能是根据用户输入的项目编号，在邻接矩阵中将对应的位置置为1，表示这两个项目是相邻的。
其中，a[i]和a[j]分别表示第i个和第j个项目的编号，(a[i] - 1) * 7 + (a[j] - 1)计算出这两个项目在邻接矩阵中的对应位置。
*/
