POJ2239 Selecting Courses（二分图最大匹配）

题目链接

N节课，每节课在一个星期中的某一节，求最多能选几节课

好吧，想了半天没想出来，最后看了题解是二分图最大匹配，好弱

建图： 每节课 与 时间有一条边

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int N =  + ;

 int vis[N], Left[N];

 vector<int> g[N];

 int n;

 bool mach(int u)

 {

     int Size = g[u].size();

     for (int i = ; i < Size; i++)

     {

         int v = g[u][i];

         if (!vis[v])

         {

             vis[v] = ;

             if (Left[v] == - || mach(Left[v]))

             {

                 Left[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int main()

 {

     while (scanf("%d", &n) != EOF)

     {

         int t, p, q;

         for (int i = ; i <= n; i++)

             g[i].clear();

         for (int i = ; i <= n; i++)

         {

             scanf("%d", &t);

             for (int j = ; j <= t; j++)

             {

                 scanf("%d%d", &p, &q);

                 g[i].push_back(p *  + q); // 可以将每一节转化成一个整数

             }

         }

         memset(Left, -, sizeof(Left));

         int ans = ;

         for (int i = ; i <= n; i++)

         {

             memset(vis, , sizeof(vis));

             if (mach(i))

                 ans++;

         }

         printf("%d\n", ans);

     }

     return ;

 }