【二分图匹配-匈牙利算法】Courses HDU - 1083

矫情吗；* 2022-06-09 10:58 230阅读 0赞

Think:  
1知识点：二分图匹配-匈牙利算法  
2题意：T组测试数据，每组测试数据输入n, m表示n门课程，m名学生，询问是否存在n名学生，使得他们满足每名学生学习了至少一门不同于其它学生的课程  
3思路：建图——二分图匹配  
4反思：for循环内改变了循环控制变量，导致for循环未正常结束

[vjudge题目链接][vjudge]

以下为Accepted代码

/*二分图匹配——行列匹配法*/
    
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    int n, m, match[404];/*match数组记录匹配关系*/
    bool vis[404], e[404][404];
    
    bool dfs(int u);
    
    int main(){
        int T, i, x, v, num;
        scanf("%d", &T);
        while(T--){
            scanf("%d %d", &n, &m);
            memset(e, 0, sizeof(e));
            for(i = 1; i <= n; i++){
                scanf("%d", &x);
                while(x--){
                    scanf("%d", &v);
                    e[i][n+v] = e[n+v][i] = 1;/*路*/
                }
            }
            num = 0;
            memset(match, 0, sizeof(match));
            for(i = 1; i <= n; i++){
                for(int j = n+1; j <= n+m; j++)/*清空上次搜索时的标记*/
                    vis[j] = 0;
                if(dfs(i))/*寻找增广路(增光路的本质就是一条路的起点和终点都是未被配对的点)，如果找到，num+1*/
                    num++;
            }
    
            if(num == n)
                printf("YES\n");
            else
                printf("NO\n");
        }
        return 0;
    }
    bool dfs(int u){
        for(int i = n+1; i <= n+m; i++){
            if(!vis[i] && e[u][i]){
       /*判断点i是否被访问过且是否存在路(u, i)*/
                vis[i] = 1;/*标记点i被访问过*/
                if(!match[i] || dfs(match[i])){
       /*如果点i未被配对或者找到了新的配对*/
                    /*更新配对信息*/
                    match[u] = i;
                    match[i] = u;
                    return true;
                }
            }
        }
        return false;
    }

[vjudge]: https://vjudge.net/problem/HDU-1083