飞行员配对方案问题飞行员配对方案问题

119 阅读 0 评论 79 点赞

我是靠谱客的博主自然草莓，这篇文章主要介绍飞行员配对方案问题飞行员配对方案问题，现在分享给大家，希望可以做个参考。

飞行员配对方案问题

题目描述

核心思路

题意：求二分图的最大匹配并且输出任意一个匹配方案

这个题可以直接用匈牙利算法来求解，时间复杂度是 $O (n m)$ 。但是也可以用网络流来求解，时间复杂度是 $O (m n)$ ，可见使用网络流算法后，效率大大增加了。

结论：

网络流中的某一条可行流对应着二分图中的一组匹配
网络流中的最大流对应着二分图的最大匹配

因此，我们想要求出二分图的最大匹配，那么就可以使用Dinic算法来求出这个网络的最大流。

那么，我们来思考一下该怎么构建这张网络图呢？

那么我们该怎么输出匹配方案呢？

我们可以遍历所有的正向边，如果发现边的容量为 $0$ ，那么说明这个边被用到了，构成了一组方案。具体就是枚举正向边，如果这条正向边的终点编号是[m+1,n]，则说明这条正向边是外籍飞行员点集和英国飞行员点集之间的一条边，然后我们判断这条边的容量 $f [i]$ 是否为0，如果为0，则说明它是一条匹配边，那么我们输出这条匹配边的起点e[i^1]，这条匹配边的终点e[i]即可。

注意：边数的计算，最坏情况是左侧点集为 $50$ ，右侧点集为 $50$ ，那么会有 $50 \times 50 = 2500$ 条边，由于网络图需要建立反向边，因此需要开2倍，即 $2500 \times 2 = 5000$ ，然后从源点 $S$ 向左侧这 $50$ 个点需要连边 $50$ ，同理从右侧这 $50$ 个点向汇点 $T$ 需要连边 $50$ ，由于需要建立反向边，因此是 $(50 + 50) \times 2 = 200$ ，因此总共需要边数为 $5000 + 200 = 5200$ 。

代码

网络流Dinic算法求解二分图最大匹配：

复制代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=5210,INF=1e8;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];
int n,m,S,T;

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

bool bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S,d[S]=0,cur[S]=h[S];
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)
                    return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)
        return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)
                d[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0;
    int flow;
    while(bfs())
    {
        while(flow=find(S,INF))
            maxflow+=flow;
    }
    return maxflow;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    //由于左侧点集编号是[1,m] 右侧点集编号是[m+1,n]
    //所以给源点和汇点的编号都不能存在于左侧点集和右侧点集中
    S=0,T=n+1;
    //从源点S向左侧点集连一条容量为1的有向边
    for(int i=1;i<=m;i++)
        add(S,i,1);
    //从右侧点集向汇点T连一条容量为1的有向边    
    for(int i=m+1;i<=n;i++)
        add(i,T,1);
    int a,b;
    //从左侧点集向右侧点集连一条容量为1的有向边 
    while(scanf("%d%d",&a,&b),a!=-1&&b!=-1)
        add(a,b,1);
    printf("%dn",dinic());
    //遍历所有的正向边  找到那些属于左侧点集和右侧点集之间的匹配边
    for(int i=0;i<idx;i+=2)
    {
        if(e[i]>m&&e[i]<=n&&!f[i])
            printf("%d %dn",e[i^1],e[i]);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=5210,INF=1e8;
int h[N],e[M],ne[M],f[M],idx;
int q[N],d[N],cur[N];
int n,m,S,T;

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

bool bfs()
{
    int hh=0,tt=0;
    memset(d,-1,sizeof d);
    q[0]=S,d[S]=0,cur[S]=h[S];
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int ver=e[i];
            if(d[ver]==-1&&f[i])
            {
                d[ver]=d[t]+1;
                cur[ver]=h[ver];
                if(ver==T)
                    return true;
                q[++tt]=ver;
            }
        }
    }
    return false;
}

int find(int u,int limit)
{
    if(u==T)
        return limit;
    int flow=0;
    for(int i=cur[u];~i&&flow<limit;i=ne[i])
    {
        cur[u]=i;
        int ver=e[i];
        if(d[ver]==d[u]+1&&f[i])
        {
            int t=find(ver,min(f[i],limit-flow));
            if(!t)
                d[ver]=-1;
            f[i]-=t;
            f[i^1]+=t;
            flow+=t;
        }
    }
    return flow;
}

int dinic()
{
    int maxflow=0;
    int flow;
    while(bfs())
    {
        while(flow=find(S,INF))
            maxflow+=flow;
    }
    return maxflow;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    //由于左侧点集编号是[1,m] 右侧点集编号是[m+1,n]
    //所以给源点和汇点的编号都不能存在于左侧点集和右侧点集中
    S=0,T=n+1;
    //从源点S向左侧点集连一条容量为1的有向边
    for(int i=1;i<=m;i++)
        add(S,i,1);
    //从右侧点集向汇点T连一条容量为1的有向边    
    for(int i=m+1;i<=n;i++)
        add(i,T,1);
    int a,b;
    //从左侧点集向右侧点集连一条容量为1的有向边 
    while(scanf("%d%d",&a,&b),a!=-1&&b!=-1)
        add(a,b,1);
    printf("%dn",dinic());
    //遍历所有的正向边  找到那些属于左侧点集和右侧点集之间的匹配边
    for(int i=0;i<idx;i+=2)
    {
        if(e[i]>m&&e[i]<=n&&!f[i])
            printf("%d %dn",e[i^1],e[i]);
    }
    return 0;
}

匈牙利算法求解二分图最大匹配：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110,M=5210;
int h[N],e[M],ne[M],idx;
int match[N];
bool st[N];
int n,m,S,T;

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

bool find(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int v=e[i];
        if(!st[v])
        {
            st[v]=true;
            if(!match[v]||find(match[v]))
            {
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&m,&n);
    int a,b;
    while(scanf("%d%d",&a,&b),a!=-1&&b!=-1)
        add(a,b);
    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i))
            res++;
    }
    printf("%dn",res);
    for(int i=m+1;i<=n;i++)
    {
        if(match[i])
            printf("%d %dn",match[i],i);
    }
    return 0;
}