首页 > 代码库 > POJ 2239 Selecting Courses【最大匹配】

POJ 2239 Selecting Courses【最大匹配】

2024-07-18 06:32:56   221人阅读

大意：

有一些课程，每个课程的上课时间在每周可能会有多节，你可以从中任选一个时间去听课，

每周七天一天12节课  告诉你每节课的上课时间问在不冲突的情况下最多上几节课？

分析：

左集合课程

右集合时间

边为该节课对应的上课时间

求最大匹配就行了

 

代码：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <vector> 5 using namespace std; 6  7 const int maxn = 305; 8 const int maxm = 12 * 7 + 10; 9 10 int mat[maxn][maxm];11 12 const int m = 12 * 7; int n; 13 14 int vis[maxm];15 int Link[maxm];16 bool Find(int u) {17     for(int i = 1; i <= m; i++) {18         if( mat[u][i] && !vis[i]) {19             vis[i] = 1;20             if(Link[i] == -1 || Find(Link[i])) {21                 Link[i] = u;22                 return true;23             }24         }25     }26     return false;27 }28 29 int solve() {30     memset(Link, -1, sizeof(Link));31     int cnt = 0;32     for(int i = 1; i <= n; i++) {33         memset(vis, 0, sizeof(vis));34         if(Find(i)) cnt++;35     }36     return cnt;37 }38 39 int main() {40     int t, a, b;41     while(EOF != scanf("%d",&n) ) {42         memset(mat, 0, sizeof(mat));43         for(int i = 1; i <= n; i++) {44             scanf("%d",&t);45             for(int j = 0; j < t; j++) {46                 scanf("%d %d",&a, &b);47                 mat[i][(a - 1) * 12 + b] = 1;48             }49         }50         printf("%d\n",solve());51     }52     return 0;53 }
View Code

 


联系
我们