Loading... **必读声明** 本博客的代码本着自由之精神而分享。如果读者在修读某门课程，而课程要求不能参阅资料，不能抄袭、套用他人代码，或者要求签署honor code等等，请立即按照要求进行操作，包括不限于立即关闭本页面停止阅读，或者在要求的位置填写参考资料的信息。本人在此已经尽到告知之义务，对所有读者的行为不负有任何责任。 # 原问题 给定n门课程，每门课占用一个学期里1~m个时段中的一些时段。比如第一门课占用1、3、5，第二门课占用2、4、6。显然同一个学生同一学期不能上两门时间冲突的课程，冲突的课程只能放在不同的学期去上。现在给出这些课程信息，求一个学生要上完这些课程至少需要的学期的数量。 原样例： ``` 5 5 2 1 3 2 2 5 1 3 0 3 1 2 4 ``` 含义： n=5, m=5（一共m个时段）； 第一个课程占用2个时段，分别是1、3； ……（直到第n=5个课程） # 建模 看上去像二分图匹配的拓展情况。但是它连二分图多重匹配都不是，因为有一些边需要在某一次中“捆绑”选择，不能拆开，此路不通。 想当然地会想到贪心，即每次选尽可能多的，从前往后扫描即可。这样可以得98分，在case 25上过不去。贪心的错误来源于选择的方式会受到扫描顺序的影响，比如下面这个答案为3的反例： ``` 5 5 2 1 3 3 1 2 4 2 1 5 2 2 4 2 4 5 ``` 只好再换一种方法。 如果根据每门课的占用时间，生成一个图，方法为：每门课为一个结点；如果两门课的时间冲突了，那就用一条边连接它们。这样，相邻的结点不能在同一学期，并且只要不相邻的结点意味着他们没有发生冲突，于是可以在同一学期。因此只要保证相邻节点的学期序号不同即可。于是问题就转化为了求简单图（无重边、无自环）的色数。 # 算法 首先建立反映冲突情况的简单图G。建立方法可以是一遍读入一边建立。对于某课程i，读入到其占用了时间time，那么令`data[i][time] = 1`。遍历i之前的课程j，若`data[j][time] = 1`，说明j也占用了时间time，课程i、j发生了冲突，那么令`g[i][j] = g[j][i] = 1 `，即在G中添加边(i, j)。 然后就是根据课本上的定理4.6.3，通过建立图G'、G''，利用`G的色数=min(G'的色数, G''的色数)`递归地求色数。 首先找到G中任意不相邻的两点i、j。则：G'为G加上边(i, j)后的图；G''为使G中i、j两点“融合”之后的图。“融合”即把i、j缩为1个点，同时与i、j关联的边都关联到融合点上去。 > 所谓定理4.6.3的原理：G'代表了i、j两点染不同颜色的情况（因为连上了所以不能染相同颜色）；G''代表了i、j染相同颜色的情况（缩成一个点了，等价于染一个颜色）。对任意i、j这个道理总是对的。因此递归的时候只需要找出任意的i、j往下递归即可，其它符合条件的i、j在同一个递归层中不必考虑。 然后对G'、G''又可以继续递归地进行这样的生成两种图的操作。一直到图成为完全图之后，就找不到不相邻的两点了，递归终止。根据完全图的色数为它的结点数，求所有生成的完全图中的最小色数，它就是原图G的色数。 在代码实现上，用一个递归函数dfs模拟上述操作即可。维护一个全局色数最小值，每生成一个完全图就更新一下，最后这个值就是所求答案。 # 代码 ```c++ // // main.cpp // t3 // // Created by Colin on 2020/05/01. // Copyright © 2020 Colin. All rights reserved. // #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int maxn = 17; class Paint { public: int n, m; bool (*graph)[maxn]; bool deleted_node[maxn]; int cn2[maxn]; int min_k = maxn + 1; Paint(const int _n, const int _m, bool (*_g)[maxn]): n(_n), m(_m), graph(_g) { memset(deleted_node, 0, sizeof(deleted_node)); for (int i = 0; i <= maxn; i++) cn2[i] = i * (i - 1) / 2; dfs(graph, deleted_node, n, m); } void dfs(bool (*_graph)[maxn], bool *deleted_node, int remained_n, int remained_e) { if (remained_e == cn2[remained_n]) // reach Kn! { min_k = min(min_k, remained_n); return; } bool g1[maxn][maxn] = { 0 }; bool g2[maxn][maxn] = { 0 }; bool deled_node_2[maxn] = { 0 }; int remained_n_1 = remained_n; int remained_n_2 = remained_n; int remained_e_1 = remained_e; int remained_e_2 = remained_e; // copy the state for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) g2[i][j] = g1[i][j] = _graph[i][j]; for (int i = 1; i <= n; i++) deled_node_2[i] = deleted_node[i]; // link i, j bool need_to_break = 0; int ii = 0, jj = 0; for (int i = 1; i <= n && !need_to_break; i++) { if (!deleted_node[i]) { for (int j = 1; j <= n && !need_to_break; j++) { if (j != i && !deleted_node[j] && !g1[i][j]) { g1[i][j] = g1[j][i] = 1; remained_e_1++; // local variable need_to_break = 1; ii = i; jj = j; } } } } dfs(g1, deleted_node, remained_n_1, remained_e_1); // combine ii, jj deled_node_2[jj] = 1; remained_n_2--; for (int k = 1; k <= n; k++) { if (!deled_node_2[k] && g2[jj][k]) { g2[jj][k] = g2[k][jj] = 0; if (g2[k][ii]) remained_e_2--; else g2[k][ii] = g2[ii][k] = 1; } } dfs(g2, deled_node_2, remained_n_2, remained_e_2); }// end function dfs }; int main() { bool conflict[maxn][maxn] = { 0 }; int data[maxn][103] = { 0 }; int n, m; int edge = 0; cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> data[i][0]; for (int j = 1; j <= data[i][0]; j++) { int time = 0; cin >> time; data[i][time] = 1; // construct conflict graph for (int course = 1; course < i; course++) { if (data[course][time]) { if (!conflict[course][i]) { edge++; conflict[course][i] = conflict[i][course] = 1; } } } } } Paint paint(n, edge, conflict); cout << paint.min_k << endl; return 0; } ``` Last modification：June 4th, 2021 at 05:18 pm © 允许规范转载 Support 如果觉得我的文章对你有用，请随意赞赏 Appreciate the author