首页 > 试题广场 >

约会匹配

[编程题]约会匹配
  • 热度指数：400 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
网易公司在七夕节前后内部都会组织相亲活动，但是由于人数众多，为了提高效率，主办方设计了一个系统。所有男生先登录系统，观看女生资料，然后在系统中登记他们自己有初步意向的女生，可以登记多个。反之女生也可以在系统中登记多个有初步意向的男生。如果某个女生和某个男生同时互相都有意向，则认定为匹配。

最终系统会取出所有系统互相都初步匹配成功的男生女生，尽量地促成他们的真实约会，约会形式是互相匹配的一男与一女单独约会，但是被选中的男生女生最多只能约会一次。问该系统最多能够促成多少次约会，让尽可能多的男生女生得到约会机会。

输入描述:
第一行输入为所有男生的id序列， 0< id数量 < 10000，用空格切分
第二行输入为所有女生的id序列， 0< id数量 < 10000，用空格切分
第三行为有已经有多少个匹配数n
下面有n行，每一行为一个已经初步互相匹配的男生女生id对，为两个数字，第一个为男生id，第二个为女生id，用空格区分


输出描述:
一个整数，最多能够促成多少次约会
示例1

输入

0 1 2
3 4 5
6
0 4
0 3
1 3
1 4
2 5
2 4

输出

3

说明

该case存在有多个互相匹配的情况，但是经过分析，0-3, 1-4, 2-5这种约会安排方法，保证尽量多的约会，同时每人只约会最多一次。
算法知识视频讲解
添加回答
Wonder2021头像 Wonder2021 
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    static boolean[][] line;
    static boolean[] used;
    static int[] matchs;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        ArrayList<String> boys = new ArrayList<String>(Arrays.asList(s.nextLine().split(" ")));
        ArrayList<String> girls = new ArrayList<String>(Arrays.asList(s.nextLine().split(" ")));
        line = new boolean[boys.size()][girls.size()];
        used = new boolean[girls.size()];
        matchs = new int[girls.size()];
        int lineCount = s.nextInt();
        s.nextLine();
        for (int i = 0; i < lineCount; i++) {
            String couple[] = s.nextLine().split(" ");
            line[boys.indexOf(couple[0])][girls.indexOf(couple[1])] = true;
        }
        s.close();
        System.out.println(match(boys.size()));
    }

    public static int match(int nBoys) {
        int sum = 0;
        Arrays.fill(matchs, -1);
        for (int i = 0; i < nBoys; i++) {
            Arrays.fill(used, false);
            if (find(i)) {
                sum++;
            }
        }
        return sum;
    }

    public static boolean find(int boy) {
        for (int i = 0; i < matchs.length; i++) {
            if (line[boy][i] && !used[i]) {
                used[i] = true;
                if (matchs[i] == -1 || find(matchs[i])) {
                    matchs[i] = boy;
                    return true;
                }
            }
        }
        return false;
    }

}

发表于 2021-08-21 10:54:11 回复(1)
Euphonium♫头像 Euphonium♫
二分图匹配 
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <ctime>
#include <numeric>
#include <sstream>
using namespace std;
typedef long long ll;
#define __IN__ freopen("in.txt", "r", stdin);
#define __OUT__ freopen("out.txt", "w", stdout);
#define __FAST__                 \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0);

#define N 10010

set<int> vis;
map<int, int> choosed;
set<int> b, g;
map<int, set<int> >mp;

bool dfs(int bid) {
    for(int gid : mp[bid]) {
        if(!vis.count(gid)) {
            vis.insert(gid);
            if(!choosed.count(gid) || dfs(choosed[gid])) {
                choosed[gid] = bid;
                return true;
            }
        }
    }
    return false;
}

int main() {
    // __FAST__
    // __IN__
    // __OUT__

    string s;
    stringstream ss;
    int x;

    getline(cin, s);
    ss << s;
    while(ss >> x)
        b.insert(x);
    getline(cin, s);
    ss.clear();
    ss << s;
    while(ss >> x)
        g.insert(x);

    int n;
    cin >> n;

    for(int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        mp[u].insert(v);
    }

    int ans = 0;
    for(int bid : b) {
        vis.clear();
        if(dfs(bid))
            ans++;
    }
    cout << ans << endl;
    return 0;
}


发表于 2021-08-07 16:19:00 回复(0)
pein531头像 pein531
通过深搜进行匹配 
from collections import defaultdict

male_ids = list(map(int, input().strip().split()))
female_ids = list(map(int, input().strip().split()))
n = int(input())
# 男女嘉宾的匹配映射
like = defaultdict(lambda: [])
for _ in range(n):
    m, f = map(int, input().strip().split())
    like[m].append(f)     # 男嘉宾m可以匹配的女嘉宾列表
    like[f].append(m)     # 女嘉宾f可以匹配的男嘉宾列表
match = dict()

def dfs(m):
    # 遍历可以和男嘉宾m配对的女嘉宾
    for f in like[m]:
        # 跳过已经访问过的女嘉宾
        if f in visit:
            continue
        visit.add(f)
        # 如果女嘉宾f还未配对，则记录m和f配对
        if f not in match:
            match[m] = f
            match[f] = m
            return True
        # 如果和女嘉宾f配对的男嘉宾还能和其他女嘉宾配对，就把女嘉宾f让给男嘉宾m，以保证更多人能够配对成功
        if dfs(match[f]):
            match[m] = f
            match[f] = m
            return True
    return False

pairs = 0
for idm in male_ids:
    visit = set()
    # 男嘉宾idm还没有配对过，则对其进行匹配
    if idm not in match:
        # 匹配成功了，对数+1
        if dfs(idm):
            pairs += 1
print(pairs)


发表于 2021-01-18 21:02:35 回复(0)
Java
菲尼克斯弗兰克头像 菲尼克斯弗兰克 
import java.util.*;
// 参考大佬的写法，加了一些注释和优化
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<String> boys = new ArrayList<>(Arrays.asList(in.nextLine().split(" ")));
        ArrayList<String> girls = new ArrayList<>(Arrays.asList(in.nextLine().split(" ")));
        int m = boys.size(), n = girls.size();
        matrix = new boolean[m][n]; // 男女生配对矩阵
        used = new boolean[n]; // 选择的女生
        matchs = new int[n]; // 遍历男生来配对女生-存储匹配的男生下标
        int len = in.nextInt();
        // 填充配对矩阵
        for (int i = 0; i < len; i++) {
            int a = in.nextInt(), b = in.nextInt();
            matrix[boys.indexOf(a+"")][girls.indexOf(b+"")] = true;
        }
        // 配对处理
        fun(m, n);
    }

    static boolean[][] matrix;
    static boolean[] used;
    static int[] matchs;
    // 遍历男生开始处理
    public static void fun(int m, int n) {
        int sum = 0;
        Arrays.fill(matchs, -1);
        for (int bidx = 0; bidx < m; bidx++) { // 遍历男生
            Arrays.fill(used, false);
            if (find(bidx, n)) { // 找到可以配对的女生
                sum++;
            }
        }
        System.out.println(sum);
    }

    // 根据矩阵去dfs查找匹配
    public static boolean find(int bidx, int n) {
        for (int gidx = 0; gidx < n; gidx++) {
            if (matrix[bidx][gidx] && !used[gidx]) { // 男女可以配对并且女孩没有遍历过
                used[gidx] = true;
                // 如果女孩原本没有匹配 或者 原来匹配的男生还有其他女生可选
                // 原来匹配的男生去换一个 这个男生让当前女孩占有
                // 比如 0-3先配对 但1要与3配对 0可以换成与4配对-> 0-4 && 1-3
                if (matchs[gidx] == -1 || find(matchs[gidx], n)) {
                    matchs[gidx] = bidx;
                    return true;
                }
            }
        }
        return false;
    }
}
发表于 2022-09-06 11:33:10 回复(0)
好难取个名字头像 好难取个名字 
import java.io.*;
import java.util.*;
public class Main{
    public static boolean match(int boy, HashMap<Integer,HashSet<Integer>> map, HashSet<Integer> vis,HashMap<Integer,Integer> p){
        for(int girl : map.get(boy)){
            if(vis.contains(girl) == false){
                vis.add(girl);
                if(p.containsKey(girl) == false || match(p.get(girl),map,vis,p)){
                    p.put(girl,boy);
                    return true;
                }
            }
        }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = " ";
        while((str = br.readLine()) != null){
            br.readLine();
            int m = Integer.parseInt(br.readLine());
            String[] str_array;
            HashMap<Integer,HashSet<Integer>> map = new HashMap<>();
            for(int i = 0; i < m; ++i){
                str_array = br.readLine().split(" ");
                int n1 = Integer.parseInt(str_array[0]);
                int n2 = Integer.parseInt(str_array[1]);
                if(map.getOrDefault(n1,null) == null) map.put(n1,new HashSet<>());
                map.get(n1).add(n2);
            }
            int result = 0;
            HashSet<Integer> vis;
            HashMap<Integer,Integer> p = new HashMap<>();
            for(int boy : map.keySet()){
                vis = new HashSet<>();
                if(match(boy,map,vis,p)) ++result;
           }
            System.out.println(result);
        }
        
    }
}

发表于 2022-07-26 15:51:49 回复(0)
Java
雨尘ovo头像 雨尘ovo 
//匈牙利算法，最大匹配，写的乱七八糟
import java.util.*;

public class Main{

    static int[] boy,gril;
    static Map<Integer,HashSet<Integer>> map;
    static Map<Integer,Integer> match;
    static HashSet<Integer> vis;
    static int ans;
    public static void main(String[] args){
        Scanner cin=new Scanner(System.in);
        while(cin.hasNext()){
            boy=Arrays.stream(cin.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            gril=Arrays.stream(cin.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int n=cin.nextInt();
            map=new HashMap<>();
            while(n--!=0){
                int x=cin.nextInt();
                int y=cin.nextInt();
                if(map.containsKey(x))
                    map.get(x).add(y);
                else{
                    HashSet<Integer> set=new HashSet<>();
                    set.add(y);
                    map.put(x,set);
                }
                if(map.containsKey(y))
                    map.get(x).add(x);
                else{
                    HashSet<Integer> set=new HashSet<>();
                    set.add(x);
                    map.put(y,set);
                }
            }
            ans=0;
            match=new HashMap<>();
            for(int i=0;i<boy.length;++i){
                vis=new HashSet<>();
                if(!match.containsKey(boy[i]))
                    if(dfs(boy[i]))
                        ++ans;
            }
            for(int i=0;i<gril.length;++i){
                vis=new HashSet<>();
                if(!match.containsKey(gril[i]))
                    if(dfs(gril[i]))
                        ++ans;
            }
            System.out.println(ans);
        }
    }

    public static boolean dfs(int index){
        HashSet<Integer> set=map.get(index);
        vis.add(index);
        for(int o:set){
            if(vis.contains(o))
                continue;
            vis.add(o);
            if(!match.containsKey(o)||dfs(match.get(o))){
                match.put(index,o);
                match.put(o,index);
                return true;
            }
        }
        return false;
    }
}

编辑于 2022-03-15 17:48:32 回复(0)
C/C++
严瑞辉头像 严瑞辉

参考其他回答给出的C++版代码，非原创

#include
#include
#include
#include
using namespace std;
unordered_map match;
bool dfs(int boy, unordered_map>& likes, unordered_set& visited) {
    for (int girl : likes[boy]) {
        if (visited.count(girl)) {
            continue;
        }
        visited.insert(girl);
        if (!match.count(girl)) {
            match[boy] = girl;
            match[girl] = boy;
            return true;
        }
        if (dfs(match[girl], likes, visited)) {
            match[boy] = girl;
            match[girl] = boy;
            return true;
        }
    }
    return false;
}
void output(vector& boys, vector& girls, int n, unordered_map>& likes) {
    int pairs = 0;
    for (int boy : boys) {
        unordered_set visited;
        if (match.count(boy) == 0) {
            if (dfs(boy, likes, visited)) {
                pairs += 1;
            }
        }
    }
    cout << pairs;
}
int main() {
    vector boys;
    int id;
    while (cin >> id) {
        boys.emplace_back(id);
        if (cin.get() == '\n') {
            break;
        }
    }
    vector girls;
    while (cin >> id) {
        girls.emplace_back(id);
        if (cin.get() == '\n') {
            break;
        }
    }
    int n;
    cin >> n;
    unordered_map> likes;
    for (int i = 0; i < n; ++i) {
        int boy, girl;
        cin >> boy >> girl;
        likes[boy].emplace_back(girl);
        likes[girl].emplace_back(boy);
    }
    output(boys, girls, n, likes);
    return 0;
}
编辑于 2021-08-07 19:27:43 回复(0)
提交观点

问题信息

iOS工程师 安卓工程师 运维工程师 算法工程师 网易 游戏研发工程师 2021 Java工程师
上传者：小小
难度：
7条回答 3277浏览

热门推荐

通过挑战的用户

相关试题

约会匹配

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号