代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define CHECKTIME() printf(%.2lf , (double)clock() / CLOCKS_PER_SEC) typedef pair pii; typedef long long llong; typedef pair pll; #define mkp make_pair /*************** Program Begin **********************/ int g[150][5005]; // class 与 requirement 的匹配关系 int req_match[5005]; // req_match[req] = class int req_n; // req 的节点数 bool v[5005]; // DFS 访问数组 class Graduation { public: bool DFS(int where) // 使用DFS进行二分匹配 { if (-1 == where) { return true; } for (int i = 0; i < req_n; i++) { if (v[i] || !g[where][i]) { continue; } v[i] = true; if (DFS(req_match[i])) { req_match[i] = where; return true; } } return false; } string moreClasses(string classesTaken, vector requirements) { string res; memset(g, 0, sizeof(g)); memset(req_match, -1, sizeof(req_match)); req_n = 0; for (int i = 0; i < requirements.size(); i++) { int s = 0; int j = 0; while (isdigit(requirements[i][j])) { s = s * 10 + (requirements[i][j] - '0'); ++j; } for (; j < requirements[i].size(); j++) { for (int k = 0; k < s; k++) { g[ (int)requirements[i][j] ][req_n + k] = 1; } } req_n += s; } bool token[200]; memset(token, 0, sizeof(token)); for (int i = 0; i < classesTaken.size(); i++) { memset(v, 0, sizeof(v)); DFS(classesTaken[i]); token[ (int)classesTaken[i]] = true; } for (int i = 33; i <= 126; i++) { if (token[i]) { continue; } memset(v, 0, sizeof(v)); if (DFS(i)) { res.push_back(i); } } for (int i = 0; i < req_n; i++) { if (-1 == req_match[i]) { res = 0; break; } } return res; } }; /************** Program End ************************/