飞行员配对方案问题

题目描述

第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。

由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 2 名飞行员，其中 1 名是英国飞行员，另 1 名是外籍飞行员。

在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

如何选择配对飞行的飞行员才能使一次派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

样例

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

网络流板子

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define ll long long
#define boost ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int sum,b[102],f[102][102];
int a[102][102],u[102],v[102],ans,n,m,x,y;
bool find(int k) {
    if (k==m+1) return 1;
    for (int i=0; i<=m+1; i++)
        if (b[i]==-1&&((f[k][i]==0&&a[k][i])||f[i][k])) {
            b[i]=k;
            if (find(i)) return 1;
        }
    return 0;
}
void update() {
    int l=m+1;
    while (l) {
        if (a[b[l]][l]) f[b[l]][l]++;
        if (a[l][b[l]]) f[l][b[l]]--;
        l=b[l];
    }
    ans++;
}
int main() {
    scanf("%d%d",&n,&m);
    for (int i=1; i<=n; i++)
        a[0][i]=1;
    for (int j=n+1; j<=m+1; j++)
        a[j][m+1]=1;
    while (x!=-1&&y!=-1)
        scanf("%d%d",&x,&y),a[x][y]=1;
    for (int i=0; i<=m+1; i++) b[i]=-1;
    b[0]=0;
    while (find(0)) {
        update();
        for (int i=1; i<=m+1; i++) b[i]=-1;
    }
    if (!ans) {
        puts("No Solution!");
        return 0;
    }
    printf("%d\n",ans);
    for (int i=1; i<=n; i++) {
        for (int j=n+1; j<=m; j++)
            if (f[i][j]) {
                printf("%d %d\n",i,j);
                break;
            }
    }
}