DAY 3 小白菜oj 1122

1122: (二分图)
时间限制: 1 Sec 内存限制: 128 MB
提交: 556 解决: 163
[提交][状态][讨论版]
题目描述
【问题背景】
n只公牛和m只母牛,
某些公牛和某些母牛互相喜欢。
但最后一只公牛只能和一只母牛建立一对一匹配。
要使得最后牛群匹配对数最大。
【输入】
第一行三个整数n, m,k( 1<= n, m <= 10000,0< k <= 100000)。
下来k行,每行两个整数 x,y,表示一条边,连接X集合中x点和Y集合的y点。
【输出】
只有一行。输出一个整数,表示牛群匹配对数最大值.

input:
5 5 9
1 2
2 2
2 3
2 5
3 1
3 3
4 1
5 3
5 4
output
5

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define N 800005
using namespace std;
int m,n;
int tot;
int head[N];
int to[N];
int nex[N];
int match[N];
bool v[N];
inline void add(int x,int y){
    ++tot;
    nex[tot]=head[x];
    head[x]=tot;
    to[tot]=y;
}
int k;
int dfs(int u){
    for(int i=head[u];i;i=nex[i]){
        int dmf=to[i];
        if(!v[dmf]){
            v[dmf]=1;
            if(!match[dmf]||dfs(match[dmf]))
            {
                match[dmf]=u;
                return 1;
            }
        }
    }
    return 0;
}
int ans=0;
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y+n);
    }
    for(int i=1;i<=n;i++){
        memset(v,0,sizeof(v));
        if(dfs(i)) ans++;
    }
    printf("%d",ans);
    return 0;
}

手动打对的第一个匈牙利~~~

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 16:38
江苏大学_2023
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
2022-12-30 20:45
门头沟学院_2023
点赞 评论 收藏
转发
头像 会员标识 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议