首页 > 代码库 > poj 1469 COURSES 解题报告

poj 1469 COURSES 解题报告

2024-07-17 23:32:55   230人阅读

题目链接：http://poj.org/problem?id=1469

题目意思：略

      for 循环中遍历的对象要特别注意，究竟是遍历课程数P 还是 学生数N，不要搞混！

     

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5  6 const int maxn = 300 + 5; 7 int match[maxn], map[maxn][maxn]; 8 int vis[maxn]; 9 int P, N, cnt;10 11 int dfs(int x)12 {13     for (int i = 1; i <= N; i++)   // 遍历学生数14     {15         if (!vis[i] && map[x][i])16         {17             vis[i] = 1;18             if (match[i] == 0|| dfs(match[i]))19             {20                 match[i] = x;21                 return 1;22             }23         }24     }25     return 0;26 }27 28 void Hungary()29 {30     cnt = 0;31     for (int i = 1; i <= P; i++)  // 遍历课程数32     {33         memset(vis, 0, sizeof(vis));34         cnt += dfs(i);35     }36 }37 38 int main()39 {40     int T, num, stu_num;41     while (scanf("%d", &T) != EOF)42     {43         while (T--)44         {45             memset(match, 0, sizeof(match));46             memset(map, 0, sizeof(map));47 48             scanf("%d%d", &P, &N);49             for (int i = 1; i <= P; i++)50             {51                 scanf("%d", &num);52                 for (int j = 1; j <= num; j++)53                 {54                     scanf("%d", &stu_num);55                     map[i][stu_num] = 1;56                 }57             }58             Hungary();59             printf("%s\n", cnt == P ? "YES" : "NO");60         }61     }62     return 0;63 }

 

     


联系
我们