本文共 1997 字，大约阅读时间需要 6 分钟。

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Problem Description

小希和Gardon在玩一个游戏：对一个N*M的棋盘，在格子里放尽量多的一些国际象棋里面的“车”，并且使得他们不能互相攻击，这当然很简单，但是Gardon限制了只有某些格子才可以放，小希还是很轻松的解决了这个问题（见下图）注意不能放车的地方不影响车的互相攻击。 

Input

输入包含多组数据， 

Output

对输入的每组数据，按照如下格式输出： 

Sample Input

3 3 4

1 2

1 3

2 1

2 2

3 3 4

1 2

1 3

2 1

3 2

Sample Output

Board 1 have 0 important blanks for 2 chessmen.

Board 2 have 3 important blanks for 3 chessmen.

Solving Ideas

题意概括: 输入一些点的坐标，把x坐标看做二分图的一部分，把y坐标看做二分图的另外一部分，求出最大匹配。

#include 
   
    #include 
    
     #define N 110int map[N][N], vis[N], match[N], m, n;int dfs(int u) {    for (int i = 1; i <= n; i++)    	if (!vis[i] && map[u][i]) {            vis[i] = 1;            if (!match[i] || dfs(match[i])) {                match[i] = u;                return 1;            }    }    return 0;}int count() {    int ans = 0;    memset(match, 0, sizeof(match));    for (int i = 1 ; i <= m; i++) {        memset(vis, 0, sizeof(vis));        if (dfs(i))            ans++;    }    return ans;}int main() {    int k, a, b, ans, counts, t = 1;    while (~scanf("%d%d%d", &m, &n, &k)) {    	counts = 0;        memset(map, 0, sizeof(map));        while (k--) {            scanf("%d%d", &a, &b);            map[a][b] = 1;        }        ans = count();        for (int i = 1; i <= m; i++)            for (int j = 1; j <= n; j++)                if (map[i][j]) {                    map[i][j] = 0;                    if (count() != ans)                        counts++;                    map[i][j] = 1;                }        printf("Board %d have %d important blanks for %d chessmen.\n", t++, counts, ans);    }    return 0;}
    
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/83040879 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！