首页 > 代码库 > XidianOJ 1048 二分图匹配模板

XidianOJ 1048 二分图匹配模板

2024-08-22 04:10:41   221人阅读

题目描述

西电ACM实验室是一个很和谐的实验室，有n个男生和m个女生组成(m>0)，尽管表面大家都全心全意地为了荣誉而战，然而经过亮亮的深入调查，我们已经知道了有一些人三心二意：每天只有99%的时间花费在切题上，而还有1%的时间在想着某位或某几位异性！作为FFF团西电分部的部长，亮亮显然不能容许这种朝三暮四的情况。但是西电ACM实验室又是一个很开明的实验室，于是亮亮决定尽可能的撮合实验室的队员！

那么问题来了，亮亮最多能撮合多少对呢？

 

 

输入

多组数据，每组数据首先是两个整数，n,m表示男女生的人数(0<n,m<=500).

接下来是一个整数l(0<=l<=200000)表示亮亮搜集得到的关系

接下来是l行，每行是两个数u,v(0<=u<n,0<=v<m)

表示第u位男生和第v位女生有情况！

由于ACM实验室是个和谐的大家庭，因此不会出现同性恋。

 

 

输出

对于每组数据，输出一个整数，表示亮亮能撮合的对数。

--正文

二分图匹配模板

用匈牙利算法解决

话说给的样例有错吧，明明u<n的给个2。。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;

int love[501][501]; // boy in the front 
int match[501];
bool visit[501];
bool dfs(int u){
    int i;
    for (i=0;i<m;i++){
        if (love[u][i] && !visit[i]){
            visit[i] = true;
            if (match[i] == -1 || dfs(match[i])){
                match[i] = u;
                return true;
            }
        }
        
    }
    return false;
}

int main(){
    while (scanf("%d %d",&n,&m) != EOF){
        int l;
        scanf("%d",&l);
        int i,j;
        memset(love,0,sizeof(love));
        for (i=0;i<501;i++){
            match[i] = -1;
        }
        
        for (i=1;i<=l;i++){
            int u,v;
            scanf("%d %d",&u,&v);
            love[u][v] = 1;
        }
        int ans = 0;
        for (i=0;i<n;i++){
            memset(visit,false,sizeof(visit));
            if (dfs(i)) ans ++;
        }
        printf("%d\n",ans);
    }    
    return 0;
}

 

XidianOJ 1048 二分图匹配模板


联系
我们