51nod 2006 飛行員匹配

2022-09-23 01:02:08 字數 1257 閱讀 5044

2006 飛行員配對(二分圖最大匹配)

第二次世界大戰時期,英國皇家空軍從淪陷國徵募了大量外籍飛行員。由皇家空軍派出的每一架飛機都需要配備在航行技能和語言上能互相配合的2名飛行員,其中1名是英國飛行員,另1名是外籍飛行員。在眾多的飛行員中,每一名外籍飛行員都可以與其他若干名英國飛行員很好地配合。如何選擇配對飛行的飛行員才能使一次派出最多的飛機。對於給定的外籍飛行員與英國飛行員的配合情況,試設計一個演算法找出最佳飛行員配對方案,使皇家空 軍一次能派出最多的飛機 。對於給定的外籍飛行員與英國飛行員的配合情況,程式設計找出一個最佳飛行員配對方案, 使皇家空軍一次能派出最多的飛機。 

input

第1行有2個正整數 m 和 n。n 是皇家空軍的飛行 員總數(n<100);m 是外籍飛行員數。外籍飛行員編號為 1~m;英國飛行員編號為 m+1~n。接下來每行有 2 個正整數 i 和 j,表示外籍飛行員 i 可以和英國飛行員 j 配合。輸入最後以 2 個-1 結束。

output

第 1 行是最佳飛行 員配對方案一次能派出的最多的飛機數 m。如果所求的最佳飛行員配對方案不存在,則輸出‘no solution!’。

input示例

5 10

1 71 8

2 62 9

2 10

3 73 8

4 74 8

5 10

-1 -1

output示例

4

對於二分圖,首先要明白其定義,什麼是二分圖,然後關於它的一系列概念(交替路,增光路等等)

然後再寫著這題會發現是裸題

這些概念,網上好多人總結的都不錯,例如下面這個

1 #include 2 #include 3 #include 4

using

namespace

std;

5const

int maxn=1e3+10;6

intans[maxn][maxn];

7int

a[maxn];

8bool find(int

i)16}17

}18return

false;19

}20intmian()

33if(s) printf("

%d\n

",s);

34else printf("

no solution!\n");

35}36return0;

37 }