首页 > 代码库 > 【 网络流24 】飞行员配对方案问题
【 网络流24 】飞行员配对方案问题
第二次世界大战时期，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 2 名飞行员，其中 1 名是英国飞行员，另 1 名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况，编程找出一个最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。
输入描述 Input Description
第 1 行有 2 个正整数 m和 n。n 是皇家空军的飞行员总数(n<100)；m 是外籍飞行员数。外籍飞行员编号为 1~m；英国飞行员编号为 m+1~n。接下来每行有 2 个正整数 i 和 j，表示外籍飞行员 i 可以和英国飞行员 j 配合。文件最后以 2个-1 结束。
输出描述 Output Description
第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。接下来 M 行是最佳飞行员配对方案。每行有 2个正整数 i 和 j，表示在最佳飞行员配对方案中，飞行员 i 和飞行员 j 配对。如果所求的最佳飞行员配对方案不存在，则输出‘No Solution!’。
样例输入 Sample Input
5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1
样例输出 Sample Output
4
1 7
2 9
3 8
5 10
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <queue> 7 using namespace std ; 8 const int inf = 1<<30 , maxn = 10000 + 11 ; 9 int m , n , head[1003] , cnt , dis[1001] , s , t , cur[1001] , sum ; 10 struct id 11 { 12 int nxt , to , vi , fro; 13 }edge[maxn<<1] ; 14 struct A 15 { 16 int a , b ; 17 } ans[1001] ; 18 19 queue< int > Q ; 20 21 inline void Init( ) 22 { 23 freopen( "air.in" , "r" , stdin ) ; 24 freopen( "air.out" , "w" , stdout ) ; 25 } 26 27 28 void add( int a , int b , int c ) 29 { 30 edge[++cnt].nxt = head[a] , edge[cnt].to = b ; 31 edge[cnt].vi = c , head[a] = cnt ; edge[cnt].fro = a ; 32 } 33 34 35 int read( ) 36 { 37 char ch = getchar( ) ; int k = 1 , ret = 0 ; 38 while( ch < ‘0‘ || ch > ‘9‘ ) { if( ch == ‘-‘ ) k = -1 ; ch = getchar( ) ; } 39 while( ch >= ‘0‘ && ch <=‘9‘ ) ret = ret * 10 + ch - ‘0‘ , ch = getchar( ) ; 40 return ret * k ; 41 } 42 43 44 void input( ) 45 { 46 m = read( ) , n = read( ) ; 47 int a, b ; cnt = 1 ; 48 s = 100<<2 , t = 100<<2 + 1 ; 49 memset( head , -1 , sizeof(head)) ; 50 while( 1 ) 51 { 52 a = read( ) , b = read( ) ; 53 if( a == -1 && b == -1 ) break ; 54 add( a , b , inf ) ; add( b , a , 0 ) ; 55 } 56 for( int x = 1 ; x <= m ; x++ ) 57 { 58 add( s , x , 1 ) ; 59 add( x , s , 0 ) ; 60 } 61 for( int x = 1 ; x <= m ; ++x ) 62 { 63 add( x+m , t , 1 ) ; 64 add( t , x+m , 0 ) ; 65 } 66 } 67 68 69 bool bfs( ) 70 { 71 memset( dis , -1 , sizeof(dis) ) ; 72 Q.push( s ) ; dis[s] = 0 ; 73 while( !Q.empty( ) ) 74 { 75 int u = Q.front( ) ; Q.pop( ) ; 76 for( int i = head[u] ; ~i ; i = edge[i].nxt ) 77 { 78 int v = edge[i].to ; 79 if( dis[v] < 0 && edge[i].vi > 0 ) 80 { 81 dis[v] = dis[u] + 1 ; 82 Q.push( v ) ; 83 } 84 } 85 } 86 return dis[t] > 0 ; 87 } 88 89 90 int dfs( int u , int tmp ) 91 { 92 if( u == t ) return tmp ; 93 int cost = 0 , an = 0 ; 94 for( int i = cur[u] ; ~i ; i = edge[i].nxt ) 95 { 96 int v = edge[i].to ; 97 if( dis[v] != dis[u] + 1 ) continue ; 98 an = dfs( v , min( tmp - cost , edge[i].to) ) ; 99 edge[i].vi -= an ; edge[i^1].vi += an ;100 if( edge[i].vi ) cur[u] = i ;101 cost += an ;102 if( cost == tmp ) return cost ; 103 }104 if( !cost ) dis[u] = -1 ;105 return cost ;106 }107 108 109 110 void sov( )111 {112 while( bfs( ) ) 113 {114 for( int x = 1 ; x <= m << 1 ; ++x ) cur[x] = head[x] ;115 sum += dfs( s , inf ) ; 116 }117 }118 119 120 bool cmp( A a , A b )121 {122 if( a.a < b.a ) return 1 ;123 if( a.a == b.a && a.b < b.b ) return 1 ;124 return 0 ;125 }126 127 128 void output( )129 {130 if( !ans )131 {132 printf( "No Solution!\n" ) ;133 return ;134 }135 printf( "%d\n" , ans ) ; int tot = 0 ;136 for( int x = 2 ; x <= cnt ; ++x )137 {138 if( !edge[x].vi && edge[x].fro != s && edge[x].nxt != t && edge[x].fro != t && edge[x].to != s && edge[x].fro < edge[x].to )139 ans[++tot].a = edge[x].fro , ans[tot].b = edge[x].to ;140 }141 sort( ans + 1 , ans + 1 + tot , cmp ) ;142 for( int x = 1 ; x <= tot ; x++ ) printf( "%d %d\n" , ans[x].a , ans[x].b ) ;143 }144 145 146 147 int main( )148 {149 Init( ) ;150 input( ) ;151 sov( ) ;152 output( ) ;153 fclose( stdin ) ;154 fclose( stdout ) ;155 return 0 ;156 }
好的没去测，存一份代码 ，
【 网络流24 】飞行员配对方案问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。