「Luogu 2756」飞行员配对方案问题

发表于 | | 阅读次数:
字数统计: 715 字

Description

题目链接：Luogu 2756

英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 $2$ 名飞行员，其中 $1$ 名是英国飞行员，另 $1$ 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。皇家空军共有 $n$ 名飞行员，其中 $m$ 名为外籍飞行员。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

数据范围：$1\le m\le m<100$

Solution

由于每个飞行员只能被选择一次，所以我们可以直接想到二分图最大匹配，显然可以用匈牙利算法或网络流解决。

对于输出方案，匈牙利算法可以直接利用匹配数组，而网络流可以判断正向边是否有流量（即反向边的残量是否不为 $0$）。

时间复杂度：$O(n^2\sqrt n)$（二分图 $\text{Dinic}$）

Code

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=205,M=2e4+5;
int n,m,tot=1,lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) dep[v]=dep[u]+1,q.push(v);
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ret=0;
    for(int i=cnr[u];i&&ret<flow;i=nxt[i]) {
        cnr[u]=i;
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ret));
            if(x) val[i]-=x,val[i^1]+=x,ret+=x;
        }
    }
    if(ret<flow) dep[u]=-1;
    return ret;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int x;
        while((x=dfs(s,t,1<<30))) ans+=x;
    }
    return ans;
}
int main() {
    scanf("%d%d",&n,&m);
    int u,v;
    while(scanf("%d%d",&u,&v)&&~u&&~v) addedge(u,v,1);
    int s=0,t=n+m+1;
    for(int i=1;i<=n;++i) addedge(s,i,1);
    for(int i=n+1;i<=m;++i) addedge(i,t,1);
    int ans=dinic(s,t);
    if(!ans) return puts("No Solution!");
    printf("%d\n",ans);
    for(int u=1;u<=n;++u) {
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(v!=s&&val[i]==0&&val[i^1]==1) printf("%d %d\n",u,v);
        }
    }
    return 0;
}
0%