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