洛谷 P2756：飞行员配对方案问题 ← 匈牙利算法

【题目来源】
https://www.luogu.com.cn/problem/P2756
https://www.acwing.com/problem/content/2177/

【题目描述】
第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。
由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 2 名飞行员，其中 1 名是英国飞行员，另 1 名是外籍飞行员。
在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。
如何选择配对飞行的飞行员才能使一次派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

【输入格式】
第 1 行有 2 个正整数 m 和 n。m 是外籍飞行员数；n 是皇家空军的飞行员总数。
外籍飞行员编号为 1∼m；英国飞行员编号为 m+1∼n。
接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。
文件最后以 2 个 −1 结束。

【输出格式】
第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。
接下来 M 行是最佳飞行员配对方案。
每行有 2 个正整数 i 和 j，表示在最佳飞行员配对方案中，外籍飞行员 i 和英国飞行员 j 配对。
如果有多种配对方案，则输出任意一种即可，方案内部配对输出顺序随意。

【数据范围】
1<m<n<100

【输入样例】
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

【输出样例】
4
1 7
2 9
3 8
5 10

【算法分析】
★ 匈牙利算法，又称为匈牙利匹配算法，是一种在多项式时间内求解任务分配问题的组合优化算法。匈牙利算法主要用于解决二分图的最大匹配问题，即在一个图中找到边数最多的匹配集合，使得集合中任意两条边都不共享顶点。
★ 匈牙利算法模板代码：https://blog.csdn.net/hnjzsyjyj/article/details/143008866

#include <bits/stdc++.h>
using namespace std;
 
const int N=505;
const int M=1e5+5;
bool st[N];
int match[N];
int h[N],ne[M],e[M],idx;
int n1,n2,m;
 
void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
 
int find(int u) {
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!st[j]) {
            st[j]=true;
            /*If girl j doesn't have a boyfriend, 
            or her previous boyfriend can book other girls he likes.
            Pairing successful. */
            if(!match[j] || find(match[j])) {
                match[j]=u;
                return true;
            }
        }
    }
    return false;
}
 
int main() {
    memset(h,-1,sizeof h);
    cin>>n1>>n2>>m;
    while(m--) {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
 
    int res=0;
    for(int i=1; i<=n1; i++) {
        memset(st,false,sizeof st);
        if(find(i)) res++;
    }
    cout<<res<<endl;
 
    return 0;
}
 
/*
in:
2 2 4
1 1
1 2
2 1
2 2
out:
2
*/

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5;
bool st[N];
int match[N];
int h[N],ne[N<<1],e[N<<1],idx;
int n,m;

void add(int a,int b) {
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

int find(int u) {
    for(int i=h[u]; i!=-1; i=ne[i]) {
        int j=e[i];
        if(!st[j]) {
            st[j]=true;
            /*If girl j doesn't have a boyfriend,
            or her previous boyfriend can book other girls he likes.
            Pairing successful. */
            if(!match[j] || find(match[j])) {
                match[j]=u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    memset(h,-1,sizeof h);
    cin>>m>>n;
    while(1) {
        int x,y;
        cin>>x>>y;
        if(x==-1 && y==-1) break;
        add(x,y);
    }

    int ans=0;
    for(int i=1; i<=m; i++) {
        memset(st,false,sizeof st);
        if(find(i)) ans++;
    }
    cout<<ans<<endl;

    for(int i=m+1; i<=n; i++) {
        if(match[i]) {
            cout<<match[i]<<" "<<i<<endl;
        }
    }

    return 0;
}

/*
in:
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

out:
4
1 7
2 9
3 8
5 10
*/

【参考文献】
https://www.acwing.com/solution/content/50487/
https://blog.csdn.net/hnjzsyjyj/article/details/143008866
https://www.acwing.com/solution/content/19848/



 

原文地址：https://blog.csdn.net/hnjzsyjyj/article/details/143020850

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！