16. 最小代价完成论文评审[200分]

题目内容

某校有 n 篇论文需要分配给教师评审。

每篇论文 i 可由文件 files[i] 对应的教师列表中任一教师评审。每篇论文至少需要一名教师评审。每位教师 t，不论被分配多少篇论文，其评审费用固定为 cost[t]。请给出参与评审教师数量最少时的总费用；若存在多种方案满足教师数最少，则选择总费用最小的方案。

输入描述

输入，共有 4 个：

• n：论文篇数
• m：教师个数
• files：二维列表，形式为 files[i][j]，具体内容为：
  • files[0] 允许评审论文 0 的教师列表，列表内有多个数值
  • files[1] 允许评审论文 1 的教师列表
  • ...
  • files[n-1] 允许评审论文 n−1 的教师列表
• cost：二维列表，列表索引 t 表示教师编号 t，列表值表示对应教师编号评审论文的费用

输出描述

返回一个整数，表示参与教师数量最少时的总费用。

约束：

• 1 ≤ n ≤ 20
• 1 ≤ m ≤ 12
• files.length 为 n，files[i] 不为空，其中元素满足 0 ≤ files[i][j] < m
• cost[t] 取值 >0，0 < t < m，累计和不超过整型值范围

样例

样例 1

输入

3
3
0,1
1,2
0,2
1,2,2

输出

3

说明： 部分教师可以评审多篇论文：

• n=3，m=3
• 评审论文 0 的教师可以为 0,1，评审论文 1 的教师可以为 0,2，评审论文 2 的教师可以为 0,2
• 方案一：编号为 0 和 2 的教师可以完成 3 篇论文评审，编号为 0 和 2 的论文分给教师 0，编号为 1 的论文分给 2，花费是 1+2=3
• 方案二：编号 1 和 2 的也可以完成 3 篇评审，花费是 2+2=4

所以选择方案一，最小费用是 3。

样例 2

输入

3 3
0
1
2
1,2,3

输出

6

说明：

• n=3，m=3，files=[[0],[1],[2]]，每篇论文只有一个教师可选
• cost=[1,2,3]，编号 0,1,2 的教师费用分别为 1,2,3
• 每篇论文只有一个教师可选，所以最小费用是 6。

样例 3

输入

4 5
0,3,4
1,3
2,4
0,4
1,1,1,3,3

输出

4

说明： 输入：

• n=4，m=5
• files=[[0,3,4],[1,3],[2,4],[0,4]]
• cost=[1,1,1,3,3]

覆盖关系：

• 教师 0 → 论文 [0,3]，费用 1
• 教师 1 → 论文 [1]，费用 1
• 教师 2 → 论文 [2]，费用 1
• 教师 3 → 论文 [0,1]，费用 3
• 教师 4 → 论文 [0,2,3]，费用 3

方案对比：

• 3 名教师 [0,1,2] 覆盖全部，费用 =3（教师多，费用少）
• 2 名教师 [1,4] 覆盖全部，费用 =4（教师少，费用次优）
• 2 名教师 [3,4] 覆盖全部，费用 =6

输出：4。解释：方案 [0,1,2] 用 3 名教师仅花费 3，比 [1,4] 的 4 更便宜，但因教师数量为 3（多于 2）。按“教师最少优先”原则淘汰该法。最终选 2 名教师的方案，在 [1,4] 和 [3,4] 中取费用最小的 4。

代码

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const lines = [];
rl.on('line', (line) => {
    lines.push(line.trim());
});

rl.on('close', () => {
    // 解析输入
    // 第1行：n m  或  n
    // 第2行：m
    // 接下来 n 行：每篇论文可选的教师列表，逗号分隔
    // 最后1行：cost 数组，逗号分隔

    let idx = 0;

    // 第一行可能同时有 n 和 m，也可能只有 n
    let firstLine = lines[idx++].split(/\s+/);
    const n = parseInt(firstLine[0]);

    let m;
    if (firstLine.length >= 2) {
        m = parseInt(firstLine[1]);
    } else {
        m = parseInt(lines[idx++]);
    }

    // 读取 n 行 files
    const files = [];
    for (let i = 0; i < n; i++) {
        const arr = lines[idx++].split(',').map(Number);
        files.push(arr);
    }

    // 读取 cost
    const cost = lines[idx++].split(',').map(Number);

    // 求解
    console.log(solution(n, m, files, cost));
});

function solution(n, m, files, cost) {
    // teacherPapers[t] = 教师 t 能评审的论文编号数组
    const teacherPapers = [];
    for (let t = 0; t < m; t++) {
        teacherPapers.push([]);
    }
    for (let i = 0; i < n; i++) {
        for (const t of files[i]) {
            teacherPapers[t].push(i);
        }
    }

    let bestNum = m + 1;       // 最少参与教师数
    let bestCost = Infinity;   // 对应最小总费用

    // 递归枚举每位教师选或不选
    function dfs(t, num, coveredCount, covered, totalCost) {
        // 剪枝：已选人数已经 >= 当前最优人数，且不可能更少
        if (num > bestNum) return;

        // 已经考虑完所有教师
        if (t === m) {
            if (coveredCount === n) {
                if (num < bestNum || (num === bestNum && totalCost < bestCost)) {
                    bestNum = num;
                    bestCost = totalCost;
                }
            }
            return;
        }

        // 不选教师 t
        dfs(t + 1, num, coveredCount, covered, totalCost);

        // 选教师 t
        const newCovered = new Set(covered);
        let newCount = coveredCount;
        for (const p of teacherPapers[t]) {
            if (!newCovered.has(p)) {
                newCovered.add(p);
                newCount++;
            }
        }
        dfs(t + 1, num + 1, newCount, newCovered, totalCost + cost[t]);
    }

    dfs(0, 0, 0, new Set(), 0);

    return bestCost;
}