本文共 2590 字，大约阅读时间需要 8 分钟。
这道题看着就是最大二分匹配的问题。用了之前POJ1274的代码就过了。
/* ID: thestor1 LANG: C++ TASK: poj1274 */#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;// See http://www.geeksforgeeks.org/maximum-bipartite-matching/ for more detailed explanationconst int MAXN = 200;const int MAXM = 200;// A DFS based recursive function that returns true if a// matching for vertex u is possiblebool DFS(int u, const bool adjMatrix[][MAXM], const int N, const int M, int match[], bool visited[]){ // Try every job one by one for (int v = 0; v < M; ++v) { // If applicant u is interested in job v and v is // not visited if (adjMatrix[u][v] && !visited[v]) { // Mark v as visited visited[v] = true; // If job 'v' is not assigned to an applicant OR // previously assigned applicant for job v (which is match[v]) // has an alternate job available. // Since v is marked as visited in the above line, match[v] // in the following recursive call will not get job 'v' again if (match[v] < 0 || DFS(match[v], adjMatrix, N, M, match, visited)) { match[v] = u; return true; } } } return false;}// Returns maximum number of matching from N to M// match: An array to keep track of the applicants assigned to jobs. // The value of match[i] is the applicant number// assigned to job i, the value -1 indicates nobody is assigned.int maximumBipartiteMatching(const bool adjMatrix[][MAXM], const int N, const int M, int match[], bool visited[]){ // Count of jobs assigned to applicants int mbm = 0; // Initially all jobs are available memset(match, -1, M * sizeof(int)); for (int u = 0; u < N; ++u) { // Mark all jobs as not seen for next applicant. memset(visited, false, M * sizeof(bool)); // Find if the applicant 'u' can get a job if (DFS(u, adjMatrix, N, M, match, visited)) { mbm++; } } return mbm;}int main(){ int N, M; bool adjMatrix[MAXN][MAXM]; int match[MAXM]; bool visited[MAXM]; while (scanf("%d%d", &N, &M) > 0) { for (int i = 0; i < N; ++i) { for (int j = 0; j < M; ++j) { adjMatrix[i][j] = false; } } for (int u = 0; u < N; ++u) { int si; scanf("%d", &si); for (int j = 0; j < si; ++j) { int v; scanf("%d", &v); v--; adjMatrix[u][v] = true; } } // printf("[debug]adjMatrix:\n"); // for (int u = 0; u < N; ++u) // { // printf("%d: ", u); // for (int v = 0; v < M; ++v) // { // printf("%d ", adjMatrix[u][v]); // } // printf("\n"); // } int mbm = maximumBipartiteMatching(adjMatrix, N, M, match, visited); printf("%d\n", mbm); } return 0; }
转载地址：http://evxli.baihongyu.com/