HDU 1281 棋盘游戏 【二分图最大匹配】

传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1281

题意概括：

有N*M大的棋盘，要在里面放尽量多的“车”，求最多能放的车的个数，和为了放最多的车有多少个各自必须放车。

解题思路：
由“车”的规则可知，同一行或者同一列只能放一个车，可以放车的点作为边，对行和列最大匹配。然后遍历去点，如果去掉该点后最大匹配数减少，则说明那个点是不能去掉的点。

AC code：

 #include <cstdio>

 #include <istream>

 #include <cstring>

 #include <algorithm>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int MAXN = ;

 struct node

 {

     int x, y;

 }cc[MAXN];

 int mmp[MAXN][MAXN];

 int linker[MAXN];

 bool used[MAXN];

 int N, M, K;

 bool Find(int u)

 {

     for(int v = ; v <= M; v++){

         if(mmp[u][v] && !used[v]){

             used[v] = true;

             if(linker[v] == - || Find(linker[v])){

                 linker[v] = u;

                 return true;

             }

         }

     }

     return false;

 }

 int Match()

 {

     int res = ;

     memset(linker, -, sizeof(linker));

     for(int u = ; u <= N; u++){

         memset(used, false, sizeof(used));

         if(Find(u)) res++;

     }

     return res;

 }

 int main()

 {

     int uu, vv, cnt = , T_case = ;

     while(~scanf("%d %d %d", &N, &M, &K)){

         memset(mmp, , sizeof(mmp));

         cnt = ;

         T_case++;

         for(int i = ; i < K; i++){

             scanf("%d%d", &uu, &vv);

             mmp[uu][vv] = ;

             cc[i].x = uu;

             cc[i].y = vv;

         }

         int ans = Match();

 //        puts("zjy");

         int ans_node = ;

         for(int i = ; i < K; i++){

             mmp[cc[i].x][cc[i].y] = ;

             if(ans > Match()) ans_node++;

             mmp[cc[i].x][cc[i].y] = ;

         }

         printf("Board %d have %d important blanks for %d chessmen.\n", T_case, ans_node, ans);

     }

     return ;

 }