【问题描述】

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

的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员， 其中1 名是英国飞

行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英

国飞行员很好地配合。 如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的

外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空

军一次能派出最多的飞机。

【解题报告】

一道二分图匹配的问题吧。我用最大流的方法做。

在二分图的基础上增加源S和汇T。

1、S向X集合中每个顶点连一条容量为1的有向边。

2、Y集合中每个顶点向T连一条容量为1的有向边。

3、XY集合之间的边都设为从A集合中的点到B集合之中的点，容量为1的有向边。

求网络最大流，流量就是匹配数，所有满流边是一组可行解。

1 program air;  2 var  3   c,g,f:array[0..101,0..101]of longint;  4   d,dv:array[0..101]of longint;  5   j,i,ans,x,y,m,n,b:longint;  6  7 procedure init;  8 begin  9   assign(input,'air.in'); 10   reset(input); 11   assign(output,'air.out'); 12   rewrite(output); 13 end; 14 15 procedure outit; 16 begin 17   close(input); 18   close(output); 19   halt; 20 end; 21 22 function min(a,b:longint):longint; 23 begin 24   if a0)and(d[u]=d[v]+1) then 36   begin 37     temp:=find(v,min(flow-find,g[u,v])); 38     inc(g[v,u],temp); 39     dec(g[u,v],temp); 40     if c[u,v]>0 then inc(f[u,v],temp) else dec(f[v,u],temp); 41     inc(find,temp); 42     if find=flow then exit(find); 43   end; 44   if d[1]>=n then exit; 45   dec(dv[d[u]]); 46   if dv[d[u]]=0 then d[1]:=n; 47   inc(d[u]); 48   inc(dv[d[u]]); 49 end; 50 51 procedure main; 52 begin 53   fillchar(f,sizeof(f),0); 54   fillchar(dv,sizeof(dv),0); 55   fillchar(d,sizeof(d),0); 56   readln(b,m); 57   n:=m+2; 58   repeat 59     readln(x,y); 60     if x<0 then break; 61     c[x+1,y+1]:=1; 62     c[1,x+1]:=1; 63     c[y+1,n]:=1; 64     g[x+1,y+1]:=1; 65     g[1,x+1]:=1; 66     g[y+1,n]:=1; 67   until true=false; 68   ans:=0; 69   dv[0]:=n; 70   while d[1]
      
       0 then writeln(i-1,' ',j-1); 84   end; 85 end; 86 87 begin 88   init; 89   main; 90   outit; 91 end.