---

题目

有M个面试官，每个面试官熟悉的编程语言是一个列表，比如[“Java”, “C++”, “Golang”]表示该面试官熟悉Java、C++和Golang三种语言。
有N个面试者，按照面试者的机试选择的语言分配面试官进行面试。现在给定每个面试官最多面试x个人，每个面试者必须被不同的面试官面试2次，请问能否给出一个匹配使得所有的面试者都能被面试到。

输入
第一行输入3个整数，M,N,x。其中0<=M<=100，0<=N<=1000
然后是M行，输入M个面试官熟悉的语言列表，多个语言之间以空格分割，语言字符串本身不存在空格
然后是N行，输入N个面试者的机试所使用的语言。

输出
第一行输出字符串true或者false，表示能否匹配。
如果能匹配，从第二行起输出一个二维数组match，如果第i个面试官面试第j个面试者，match[i][j]== 1，否则match[i][j]==0。二维数组元素之间采用单个空格分割。如果有多种匹配，只需要输出其中一种正确的匹配即可

样例1
输入:

4 6 4
Java C++ Python
Python
C++ Java
Python
Java
Python
C++
Python
C++
Java

输出:

true
1 0 1 0 1 1
0 1 0 1 0 0
1 0 1 0 1 1
0 1 0 1 0 0

分析

(回溯/dfs)

此题类似于 LeetCode 51. N 皇后，可以对比一起做

题目要求输出是否能够安排好面试，能则输出安排方案。
能安排好意味着结果矩阵每列1的个数为2，且每行1的个数不超过k.

解题思路如下：

• 面试官可能熟悉多种语言，因此存入二维数组interviewer中，面试者的语言存入一维数组interviewee中
• 根据两个数组interviewer与interviewee，构造匹配矩阵match, match[i][j] = 1表示 i 面试官可以面试 j 面试者， 相反match[i][j] = 0表示 i 面试官与 j 面试者语言不匹配
• 然后根据 match 矩阵回溯搜索可行解，一旦找到可行解，则此题返回true, 并输出表示安排方案的结果矩阵，如果穷举结果都不可行，则返回false, 没有可行的安排方案。
• 关键在于回溯，从第1列开始安排，选择两个面试官将对应位置置为1，然后是第2列…，需要明确以下值
  • 结束条件：当安排完最后一列，则此时的board矩阵为一个可行方案
  • 选择列表：对于每一个面试者，即矩阵的每一列，可以选择的是匹配矩阵match为1的面试官，从中选择两个作为当前选择，同时要判断将这两处置为1时，矩阵合法（即行和<=k）

代码（C++）

#include 
#include 
#include 
using namespace std;

bool flag = false;
vector<vector<int> > res;

bool isSame(string a, string b) {
    if (a.size() != b.size()) return false;
    for (int i = 0; i < a.size(); i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

bool isValid(vector<vector<int> >& board, vector<vector<int> >& match, int col, int i, int j, int k) {
    if (match[i][col] != 1 || match[j][col] != 1) return false; 
    
    int sum1 = 0;  // 第i行的1的个数
    for (int s = 0; s < board[i].size(); s++) {
        if (board[i][s] == 1) sum1++;
    }

    int sum2 = 0;  // 第j行的1的个数
    for (int s = 0; s < board[j].size(); s++) {
        if (board[j][s] == 1) sum2++;
    }
    
    return sum1 <= k && sum2 <= k;
}

// board记录所做选择，match是面试官与面试者的匹配矩阵，col是当前列，k为每行1个数的阈值
void backtrack(vector<vector<int> >& board, vector<vector<int> >& match, int col, int k) {
    if (col == board[0].size() ) {
        flag = true;
        res = board;
        return;
    }

    int m = board.size();
    for (int i = 0; i < m; i++) { 
        for (int j = i + 1; j < m; j++) {
            if (!isValid(board, match, col, i, j, k)) continue;
            board[i][col] = 1;
            board[j][col] = 1;
            backtrack(board, match, col + 1, k);
            board[i][col] = 0;
            board[j][col] = 0;
        }
    }
}

int main() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<vector<string> > interviewer; // m个面试官的语言
    vector<string> interviewee;  // n个面试者的语言

    cin.get(); //读走'\n'
    int s = m;
    while (s--) {  // 存入interviewer数组
        vector<string> vec;
        string line, t;
        getline(cin, line);
        stringstream linestream;
        linestream.str(line);
        while (linestream >> t) vec.push_back(t);
        interviewer.push_back(vec);
    }

    s = n;
    while (s--) {  // 存入interviewee数组
        string str;
        cin >> str;
        interviewee.push_back(str);
    }
    
    vector<vector<int> > match(m, vector<int>(n, 0)); //匹配关系
    // 构造match矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int k = 0; k < interviewer[j].size(); k++) {
                //cout << interviewee[i] << " " << interviewer[j][k] << endl;
                if (isSame(interviewee[i], interviewer[j][k]))
                    match[j][i] = 1;
            }
        }
    }

    vector<vector<int> > board(m, vector<int>(n, 0));
    backtrack(board, match, 0, k);

	// 输出结果
    cout << endl << "**************res*************" << endl;
    if (!flag) cout << "false" << endl;
    else {
        cout << "true" << endl;  // col = 0-n
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cout << res[i][j] << " ";
            }
            cout <<endl;
        }
    }

	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

运行结果

输入

4 6 4
Java C++ Python
Python
C++ Java
Python
Java
Python
C++
Python
C++
Java

输出结果

输入

4 6 4
Java C++ Python
Python
C++
Python
Java
Python
C++
Python
C++
Java

输出结果