匈牙利算法 cojs.tk 搭配飛行員

cojs.tk  搭配飛行員

★★☆   輸入檔案：

flyer.in

   輸出檔案：

flyer.out

   簡單對比

時間限制：1 s   記憶體限制：128 MB

【問題描述】

    飛行大隊有若幹個來自各地的駕駛員，專門駕駛一種型号的飛機，這種飛機每架有兩個駕駛員,需一個正駕駛員和一個副駕駛員。由于種種原因，例如互相配合的問題，有些駕駛員不能在同一架飛機上飛行，問如何搭配駕駛員才能使出航的飛機最多。

如圖，假設有10個駕駛員，如圖中的V1，V2，…，V10就代表達10個駕駛員,其中V1，V2，V3，V4，V5是正駕駛員,V6，V7，V8，V9，V10是副駕駛員。如果一個正駕駛員和一個副駕駛員可以同機飛行，就在代表他們兩個之間連一條線,兩個人不能同機飛行，就不連。例如V1和V7可以同機飛行，而V1和V8就不行。請搭配飛行員，使出航的飛機最多。注意:因為駕駛工作分工嚴格,兩個正駕駛員或兩個副駕駛員都不能同機飛行.

【輸入格式】

輸入檔案有若幹行

第一行，兩個整數n與n1，表示共有n個飛行員(2<=n<=100),其中有n1名飛行員是正駕駛員.

下面有若幹行,每行有2個數字a,b。表示正駕駛員a和副駕駛員b可以同機飛行。

注:正駕駛員的編号在前,即正駕駛員的編号小于副駕駛員的編号.

【輸出格式】

輸出檔案有一行

第一行，1個整數，表示最大起飛的飛機數。

【輸入輸出樣例】

輸入檔案名： flyer.in

10 5 

1 7 

2 6 

2 10 

3 7 

4 8 

5 9 

輸出檔案名：flyer.out

4

1 #include<vector>
 2 #include<iostream>
 3 using namespace std;
 4 #include<cstdio>
 5 #include<cstring>
 6 #define N 110
 7 bool visit[N]={false};
 8 int n,n1;
 9 struct Edge{
10     int v,last;
11 };
12 int m=-1,head[N],Link[N];
13 vector<Edge>edge;
14 void add_edge(int u,int v)
15 {
16     Edge e;
17     e.v=v;
18     e.last=head[u];
19     head[u]=++m;
20     edge.push_back(e);
21 }
22 void input()
23 {
24     scanf("%d%d",&n,&n1);
25     int u,v;
26     while(scanf("%d%d",&u,&v)==2)
27     {
28         add_edge(u,v);
29     }
30 }
31 bool xylfind(int k)
32 {
33     for(int l=head[k];l!=-1;l=edge[l].last)
34     {
35         if(!visit[edge[l].v])
36         {
37             visit[edge[l].v]=true;
38             if(!Link[edge[l].v]||xylfind(Link[edge[l].v]))
39             {
40                 Link[edge[l].v]=k;
41                 return true;
42             }
43         }
44     }
45     return false;
46 }
47 int main()
48 {
49     freopen("flyer.in","r",stdin);
50     freopen("flyer.out","w",stdout);
51     memset(head,-1,sizeof(head));
52     input();
53     int ans=0;
54     for(int i=1;i<=n1;++i)
55     {
56         memset(visit,false,sizeof(visit));
57         if(xylfind(i)) ans++;
58     }
59     printf("%d\n",ans);
60     fclose(stdin);
61     fclose(stdout);
62     return 0;
63 }