P2756 飛行員配對方案問題

文章目錄

• • 題目背景
  • 題解：
  • 代碼：

題目背景

第二次世界大戰(zhàn)期間，英國皇家空軍從淪陷國征募了大量外籍飛行員。由皇家空軍派出的每一架飛機都需要配備在航行技能和語言上能互相配合的兩名飛行員，其中一名是英國飛行員，另一名是外籍飛行員。在眾多的飛行員中，每一名外籍飛行員都可以與其他若干名英國飛行員很好地配合。

題目描述

一共有 n 個飛行員，其中有 m 個外籍飛行員和 (n - m) 個英國飛行員，外籍飛行員從 1 到 m
編號，英國飛行員從 m + 1 到 n 編號。
對于給定的外籍飛行員與英國飛行員的配合情況，試設(shè)計一個算法找出最佳飛行員配對方案，使皇家空軍一次能派出最多的飛機。

輸入格式

輸入的第一行是用空格隔開的兩個正整數(shù)，分別代表外籍飛行員的個數(shù) m 和飛行員總數(shù) n。 從第二行起到倒數(shù)第二行，每行有兩個整數(shù) u,v，代表外籍飛行員 u 可以和英國飛行員 v 配合。 輸入的最后一行保證為 -1，代表輸入結(jié)束。

輸出格式

本題存在 Special Judge。 請輸出能派出最多的飛機數(shù)量，并給出一種可行的方案。
輸出的第一行是一個整數(shù)，代表一次能派出的最多飛機數(shù)量，設(shè)這個整數(shù)是k。 第 2 行到第 k+1 行，每行輸出兩個整數(shù)
u,v，代表在你給出的方案中，外籍飛行員 u 和英國飛行員 v 配合。這 k 行的 u 與 v 應(yīng)該互不相同。

輸入輸出樣例
輸入 #1復(fù)制

5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8 5 10 -1 -1

輸出 #1復(fù)制

4 1 7 2 9 3 8 5 10

說明/提示

【數(shù)據(jù)范圍與約定】

對于 100% 的數(shù)據(jù)，保證1≤m≤n<100，1≤u≤m<v≤n，同一組配對關(guān)系只會給出一次。 【提示】

請注意輸入的第一行先讀入 m，再讀入 n。

題解：

歡迎開始我們的網(wǎng)絡(luò)流24題
根據(jù)題意我們可以知道這是一個二分圖，其實是一個二分圖最大匹配的問題，對于二分圖我們用網(wǎng)絡(luò)流的方式來解決
二分圖有A和B兩個大集合，A和B之間有線，A和B自身內(nèi)部無線，相當(dāng)于A和B分別都在自己的層數(shù)。我們在創(chuàng)立一個源點s，再創(chuàng)一個終點t，s指向A中所有點，B中所有點指向t，邊的流量我們設(shè)為1，這樣不就構(gòu)成一個網(wǎng)絡(luò)流問題

以上說的是對于二分圖最大匹配通用解法，具體針對本題
我們先構(gòu)建從S到A的邊，再構(gòu)建從B到T的邊，然后讀入數(shù)據(jù)，
我們在讀入時，外籍飛行員是u，英國飛行員的編號為v+n
最后我們輸出時還要輸出所匹配的結(jié)果，因此我們用到一個數(shù)組ansk[i]：標(biāo)號為i的外籍飛行員與標(biāo)號為ansk[i]-n的英雄飛行員對應(yīng)
pre用來存在一條增廣路中，節(jié)點的前一個節(jié)點和與之相連的邊
其他的都是正常Ek算法

代碼：

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; int n,m; const int mx=1<<30; struct Node{int v;int val;int nxt; }node[5010]; int top=1; int s=1008,t=1009; int ansk[1050];//標(biāo)號為i的外籍飛行員和標(biāo)號為ansk[i]-n的英國飛行員對應(yīng) struct P{int fa;//前節(jié)點 int edge; }pre[1010];//在一條增廣路中，節(jié)點的前一個節(jié)點和與之相連的邊 int head[1010]; int vis[1010];//點是否查詢過 inline int Read(){int x=0,f=1;char c=getchar();while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f; } inline void addedge(int u,int v,int val){node[++top].v=v;node[top].val=val;node[top].nxt=head[u];head[u]=top; } bool addroad(){memset(pre,-1,sizeof(pre));memset(vis,0,sizeof(vis));queue<int>q;q.push(s);vis[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i;i=node[i].nxt){int v=node[i].v;int val=node[i].val;//記錄，方便后面輸出 if(val!=0&&vis[v]==0){pre[v].fa=u;pre[v].edge=i;if(v==t)return 1;q.push(v);vis[v]=1;}}}return 0; }//尋找增廣路 int EK(){int ans=0;while(addroad()){int mi=mx;for(int i=t;i!=s;i=pre[i].fa){mi=min(mi,node[pre[i].edge].val);}for(int i=t;i!=s;i=pre[i].fa){ansk[pre[i].fa]=i;node[pre[i].edge].val-=mi;node[pre[i].edge^1].val+=mi; }ans+=mi;}return ans; }//EK求最大流 int main(){m=Read(),n=Read();register int i;//英國飛行員用n+i號點表示，外籍飛行員用i號點表示 for(i=1;i<=n;i++){addedge(i+n,t,1);//構(gòu)建從B到t addedge(t,i+n,0);//使所有英國空軍和匯點相連 }for(i=1;i<=m;i++){addedge(s,i,1);//構(gòu)建從s到A addedge(i,s,0);//使所有外籍空軍和源點相連}int u,v;while(1){u=Read(),v=Read();if(u==-1&&v==-1)break;addedge(u,v+n,1);//讀入數(shù)據(jù) addedge(v+n,u,0);} printf("%d\n",EK());for(i=1;i<=n;i++){if(ansk[i]!=0)printf("%d %d\n",i,ansk[i]-n);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的P2756 飞行员配对方案问题【网络流24题】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。