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

亦凉 2022-06-04 00:29 182阅读 0赞

Think:  
1知识点：二分图匹配  
2题意：在棋盘内选定一些位置，在这些位置中选取部分位置放置“车”，要求每一行或者每一列不能出现多余1个“车”，询问最多放置几个“车”和那些位置是需要重要的(即若不存在，则最多放置数量会减少)  
3思路：  
（1）：X集合：\{xi\}  
（2）：Y集合：\{yi\}  
（3）：[思路借鉴博客链接][Link 1]  
![这里写图片描述][SouthEast]  
4思考：  
（1）：建立有向图  
（2）：match\[yi\] = xi

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Node{
        int x, y;
    }rec[14014];
    
    int n, m, gra[104][104], vis[104], match[104];
    
    int dfs(int u);
    int max_p();
    
    int main(){
        int cas = 1, k;
        while(~scanf("%d %d %d", &n, &m, &k)){
            memset(gra, 0, sizeof(gra));
            for(int i = 0; i < k; i++){
                scanf("%d %d", &rec[i].x, &rec[i].y);
                gra[rec[i].x][rec[i].y] = 1;
            }
            int ans = max_p();
            int num = 0, t;
            for(int i = 0; i < k; i++){
                gra[rec[i].x][rec[i].y] = 0;
                t = max_p();
                gra[rec[i].x][rec[i].y] = 1;
                if(t < ans) num++;
            }
            printf("Board %d have %d important blanks for %d chessmen.\n", cas++, num, ans);
        }
        return 0;
    }
    int dfs(int u){
        for(int i = 1; i <= m; i++){
            if(!vis[i] && gra[u][i]){
                vis[i] = 1;
                if(match[i] == 0 || dfs(match[i])){
                    match[i] = u;/*match[yi] = xi*/
                    return 1;
                }
            }
        }
        return 0;
    }
    int max_p(){
        memset(match, 0, sizeof(match));
        int cnt = 0;
        for(int i = 1; i <= n; i++){
            memset(vis, 0, sizeof(vis));
            if(dfs(i)) cnt++;
        }
        return cnt;
    }

[Link 1]: http://blog.csdn.net/u013615904/article/details/45767313
[SouthEast]: /images/20220604/484441a670704feda4e547f6062fe73a.png
[vjudge]: https://vjudge.net/problem/HDU-1281