搜索
查看: 268|回复: 4
打印 上一主题 下一主题

2019.1.20

[复制链接]
楼主
发表于 2019-1-20 17:48:25 | 显示全部楼层
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
int n,m,t,e[401][401]={0},match[401]={0},book[401]={0},sum=0;
int dfs(int u){
        for(int i=1;i<=m;i++){
                if(book[i]==0 && e[u][i]==1){
                        book[i]=1;
                        if(match[i]==0 || dfs(match[i])){
                                match[i]=u;
                                return 1;
                        }
                }
        }
        return 0;
}
int main(){
        scanf("%d%d%d",&n,&m,&t);
        for(int i=1;i<=n;++i){
                for(int j=1;j<=m;++j){
                        e[i][j]=1;
                }
        }
        for(int i=1;i<=t;++i){
                int x,y;
                scanf("%d%d",&x,&y);
                e[x][y]=0;
        }
        for(int i=1;i<=n;++i){
                for(int j=1;j<=m;++j) book[j]=0;
                        if(dfs(i)==1)
                                sum++;
        }
        printf("%d",sum);
       
        return 0;
}
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

广播台
特别关注
快速回复 返回顶部 返回列表