必读声明

本博客的代码本着自由之精神而分享。如果读者在修读某门课程,而课程要求不能参阅资料,不能抄袭、套用他人代码,或者要求签署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模拟上述操作即可。维护一个全局色数最小值,每生成一个完全图就更新一下,最后这个值就是所求答案。

代码

//
//  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:May 3rd, 2020 at 01:28 am
如果觉得我的文章对你有用,请随意赞赏