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

输入

第1行有2个正整数 m 和 n。n 是皇家空军的飞行 员总数(n<100);m 是外籍飞行员数。外籍飞行员编号为 1~m;英国飞行员编号为 m+1~n。接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。输入最后以 2 个-1 结束。

输出

第 1 行是最佳飞行 员配对方案一次能派出的最多的飞机数 M。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。

输入样例

输出样例

4

最大二分图匹配复习，邻接表存图。
代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define MAX 101

using namespace std;

int m,n;

int belong[MAX];

int vis[MAX];

int first[MAX * MAX],next[MAX * MAX];

int a[MAX * MAX],b[MAX * MAX],c;

int Find(int x) {///为x找匹配

    for(int k = first[x];k != -;k = next[k]) {

        if(vis[b[k]]) continue;

        vis[b[k]] = ;

        if(!belong[b[k]] || Find(belong[b[k]])) {///如果x的邻接点 没有被别的选 或者 选他的那个点可以有别的选择

            belong[b[k]] = x;

            return ;

        }

    }

    return ;

}

int main() {

    scanf("%d%d",&m,&n);

    memset(first,-,sizeof(first));

    while(~scanf("%d%d",&a[c],&b[c]) && a[c] != - && b[c] != -) {

        next[c] = first[a[c]];

        first[a[c]] = c;

        c ++;

    }

    int ans = ;

    for(int i = ;i <= m;i ++) {

        memset(vis,,sizeof(vis));

        if(Find(i)) ans ++;

    }

    if(ans)printf("%d\n",ans);

    else printf("No Solution!\n");

}

巴特西

51nod 2006 飞行员配对

输入

输出

输入样例

输出样例

最新文章

热门文章