题意分析

题目要求计算学生在特定条件下完成所有必修课程所需的最短学期数。关键条件包括：

1. 学期安排：

   • 每年只有秋季（$F$）和春季（$S$）两个学期，学期计数从秋季开始。
   • 部分课程仅在特定学期开设（$F$或$S$），部分课程两学期均开（$B$）。

2. 先修课程限制：

   • 每门课程可能有$0$到$5$门先修课程，必须先完成所有先修课程才能选修该课程。

3. 课程容量限制：

   • 每学期最多选修$m$门课程（$2 \leq m \leq 6$）。

4. 目标：

   • 合理安排每学期的选课，使得在满足先修条件和学期限制的情况下，用最少的学期完成所有课程。

示例解释

第一个测试用例：

• 课程：$mt42$（F）、$cs123$（S）、$cs456$（S）、$cs789$（B）。
• 先修关系：$cs456$需要$cs123$和$mt42$，$cs789$需要$cs456$。
• 每学期最多选修$6$门课程（实际未达到限制）。
• 最短学期数为$5$（秋季$mt42$→春季$cs123$→春季$cs456$→秋季$cs789$）。

解题思路

关键点分析

1. 课程依赖关系：

   • 用有向无环图（$DAG$）表示课程间的先修关系，边$u \rightarrow v$表示$u$是$v$的先修课程。
   • 需要拓扑排序来确定课程选修顺序。

2. 学期限制：

   • 课程只能在允许的学期选修（$F$、$S$或$B$）。
   • 每学期选修课程数不超过$m$。

3. 动态规划或状态搜索：

   • 由于课程数$n \leq 12$，可用状态压缩或广度优先搜索（$BFS$）枚举所有可能的选课状态。
   • 状态包括：已完成的课程、当前学期（$F$或$S$）、已用学期数。

解决步骤

1. 输入处理：

   • 读取课程信息和先修关系，构建$DAG$。
   • 记录每门课程的开课学期。

2. 状态表示：

   • 用位掩码表示已完成的课程（如$mask$的第$i$位表示第$i$门课程是否完成）。
   • 当前学期（$0$=秋季，$1$=春季）。
   • 已用学期数。

3. 广度优先搜索（$BFS$）：

   • 初始状态：$mask=0$（无课程完成），学期$0$（秋季），学期数$1$。
   • 对于每个状态，枚举所有可选课程（满足先修条件且当前学期允许）。
   • 从可选课程中选择不超过$m$门的组合，生成新状态。
   • 如果新状态达到$mask=2^n-1$（所有课程完成），返回当前学期数。

4. 优化：

   • 使用优先队列（$Dijkstra$）优先处理学期数少的状态。
   • 避免重复处理相同状态（$mask$和学期）。

算法复杂度

• 状态数：$O(2^n \times 2)$（$2^n$为课程子集，$2$为学期类型）。
• 每状态处理：$O(\binom{n}{m})$（选择最多$m$门课程）。
• 总复杂度：$O(2^n \times \binom{n}{m})$，对于$n \leq 12$和$m \leq 6$是可接受的。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;

#define max(a,b) ((a) < (b) ? (b) : (a))
typedef long long LL;
#define eps 1e-8

const int maxn = (1<<12)+10;
const int inf = 1e9;
bool dp[2][maxn];
int pre[15];
map<string, int> course;
int p[15], n, m, sem[15];
char buffer[10];
string s;

void init()
{
    course.clear();
    memset(pre, 0, sizeof(pre));
}

void input()
{
    for (int i = 1; i <= n; ++i)
    {
        scanf("%s", buffer);
        s = buffer;
        course[s] = i;
    }
    for (int i = 0; i < n; ++i)
    {
        scanf("%s", buffer);
        string temp = buffer;
        int x = course[temp];
        scanf("%s", buffer);
        if (buffer[0] == 'B') sem[x] = 2;
        else if (buffer[0] == 'F') sem[x] = 1;
        else if (buffer[0] == 'S') sem[x] = 0;
        int k;
        scanf("%d", &k);
        while (k--)
        {
            int y;
            scanf("%s", buffer);
            temp = buffer;
            y = course[temp];
            pre[x] += p[y];
        }
    }
}

void dfs(int prer, int state, int cur, int rest, int pos, int term)
{
    dp[pos][state] = true;
    if (rest == 0 || cur > n) return;
    if ((pre[cur] & prer) == pre[cur] && !(state & (p[cur])) && (sem[cur] == 2 || (term % 2) == sem[cur]))
        dfs(prer, state + p[cur], cur + 1, rest - 1, pos, term);
    dfs(prer, state, cur + 1, rest, pos, term);
}

void solve()
{
    int max_s = 1 << n;
    memset(dp, false, sizeof(dp));
    dp[1][0] = true;
    int cnt;
    for (cnt = 1; ; ++cnt)
    {
        for (int s = 0; s < max_s; ++s)
        {
            if (!dp[cnt % 2][s]) continue;
            dfs(s, s, 1, m, (cnt + 1) % 2, cnt);
        }
        if (dp[(cnt + 1) % 2][max_s - 1]) break;
        memset(dp[cnt % 2], false, sizeof(dp[cnt % 2]));
    }

    printf("The minimum number of semesters required to graduate is %d.\n", cnt);
}

int main()
{
    p[1] = 1;
    for (int i = 2; i <= 12; ++i) p[i] = p[i - 1] << 1;
    while (scanf("%d%d", &n, &m) == 2)
    {
        if (n == -1 && m == -1) return 0;
        init();
        input();
        solve();
    }
}