P2756 飛行員配對方案問題

題目背景

第二次世界大戰(zhàn)時期..

題目描述

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

對于給定的外籍飛行員與英國飛行員的配合情況，編程找出一個最佳飛行員配對方案，使皇家空軍一次能派出最多的飛機。

輸入格式

第 1 行有 2 個正整數 m 和 n。n 是皇家空軍的飛行員總數(n<100)；m 是外籍飛行員數(m<=n)。外籍飛行員編號為 1~m；英國飛行員編號為 m+1~n。

接下來每行有 2 個正整數 i 和 j，表示外籍飛行員 i 可以和英國飛行員 j 配合。最后以 2個-1 結束。

輸出格式

第 1 行是最佳飛行員配對方案一次能派出的最多的飛機數 M。接下來 M 行是最佳飛行員配對方案。每行有 2個正整數 i 和 j，表示在最佳飛行員配對方案中，飛行員 i 和飛行員 j 配對。如果所求的最佳飛行員配對方案不存在，則輸出‘No Solution!’。

輸入輸出樣例

輸入 #1復制

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復制

4 1 7 2 9 3 8 5 10

思路：

二分圖最大匹配的裸題，可以用匈牙利直接求解，同時用linker數組輸出具體的方案。

或者用最大流求解，

把外籍飛行員 化為左邊的點

英國飛行員 化為右邊的點，

即一個左右點之間的最大匹配問題，

然后建立一個超級源點0，將超級源點和所有左邊的點相連，流量為1.

建立一個超級匯點n+1，將超級匯點和所有右邊的點相連，流量為1.

然后左邊和右邊的連邊即為題目給的可行邊，流量也為1.

然后跑最大流，就是最佳匹配方案數。

我是用的ISAP算法跑的網絡流。

中間邊如果殘余流量為0，那么這個邊的兩個節(jié)點就是匹配方案中的一個匹配對。

網絡流代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int* p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ #define N 1000 #define INF 100000000 struct Edge {int from, to, cap, flow; };struct ISAP {int n, m, s, t;vector<Edge>edges;vector<int>G[N];bool vis[N];int d[N], cur[N];int p[N], num[N]; //比Dinic算法多了這兩個數組，p數組標記父親結點，num數組標記距離d[i]存在幾個void addedge(int from, int to, int cap){edges.push_back((Edge) {from, to, cap, 0});edges.push_back((Edge) {to, from, 0, 0});int m = edges.size();G[from].push_back(m - 2);G[to].push_back(m - 1);}int Augumemt(){int x = t, a = INF;while (x != s) //找最小的殘量值{Edge&e = edges[p[x]];a = min(a, e.cap - e.flow);x = edges[p[x]].from;}x = t;while (x != s) //增廣{edges[p[x]].flow += a;edges[p[x] ^ 1].flow -= a;x = edges[p[x]].from;}return a;}void bfs()//逆向進行bfs{memset(vis, 0, sizeof(vis));queue<int>q;q.push(t);d[t] = 0;vis[t] = 1;while (!q.empty()){int x = q.front(); q.pop();int len = G[x].size();for (int i = 0; i < len; i++){Edge&e = edges[G[x][i]];if (!vis[e.from] && e.cap > e.flow){vis[e.from] = 1;d[e.from] = d[x] + 1;q.push(e.from);}}}}int Maxflow(int s, int t) //根據情況前進或者后退，走到匯點時增廣{this->s = s;this->t = t;int flow = 0;bfs();memset(num, 0, sizeof(num));for (int i = 0; i < n; i++)num[d[i]]++;int x = s;memset(cur, 0, sizeof(cur));while (d[s] < n){if (x == t) //走到了匯點，進行增廣{flow += Augumemt();x = s; //增廣后回到源點}int ok = 0;for (int i = cur[x]; i < G[x].size(); i++){Edge&e = edges[G[x][i]];if (e.cap > e.flow && d[x] == d[e.to] + 1){ok = 1;p[e.to] = G[x][i]; //記錄來的時候走的邊，即父邊cur[x] = i;x = e.to; //前進break;}}if (!ok) //走不動了，撤退{int m = n - 1; //如果沒有弧，那么m+1就是n，即d[i]=nfor (int i = 0; i < G[x].size(); i++){Edge&e = edges[G[x][i]];if (e.cap > e.flow)m = min(m, d[e.to]);}if (--num[d[x]] == 0)break; //如果走不動了，且這個距離值原來只有一個，那么s-t不連通，這就是所謂的“gap優(yōu)化”num[d[x] = m + 1]++;cur[x] = 0;if (x != s)x = edges[p[x]].from; //退一步，沿著父邊返回}}return flow;} }; ISAP gao; int n, m;int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);du2(m, n);int x, y;while (~scanf("%d %d", &x, &y)){if (x + y == -2){break;}gao.addedge(x, y, 1);}// gao.s = 0;// gao.t = n + 1;repd(i, 1, m){gao.addedge(0, i, 1);}repd(i, m + 1, n){gao.addedge(i, n + 1, 1);}gao.n = n + 2;printf("%d\n", gao.Maxflow(0, n + 1) );repd(i, 1, m){for (auto yy : gao.G[i]){Edge temp = gao.edges[yy];int v = temp.to;if (v > m && v <= n && temp.flow == 1){printf("%d %d\n", i, v );}}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

匈牙利代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl #define du3(a,b,c) scanf("%d %d %d",&(a),&(b),&(c)) #define du2(a,b) scanf("%d %d",&(a),&(b)) #define du1(a) scanf("%d",&(a)); using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {a %= MOD; if (a == 0ll) {return 0ll;} ll ans = 1; while (b) {if (b & 1) {ans = ans * a % MOD;} a = a * a % MOD; b >>= 1;} return ans;} void Pv(const vector<int> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%d", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}} void Pvl(const vector<ll> &V) {int Len = sz(V); for (int i = 0; i < Len; ++i) {printf("%lld", V[i] ); if (i != Len - 1) {printf(" ");} else {printf("\n");}}}inline void getInt(int* p); const int maxn = 10010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/ int linker[maxn * 2]; bool used[maxn * 2]; std::vector<int> son[maxn]; bool dfs(int u) {for (auto v : son[u]) {if (!used[v]) {used[v] = true;if (linker[v] == -1 || dfs(linker[v])) {linker[v] = u;return true;}}}return false; }int n, m; int hungarian() {int res = 0;for (int i = 0; i <= n; i++) {linker[i] = -1;}for (int u = 1; u <= m; u++) {for (int i = 1; i <= n ; i++){used[i] = 0;}// 根據題目判斷是否改memsetif (dfs(u)){res++;}}return res; } int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);du2(m, n);int x, y;while (~scanf("%d %d", &x, &y)){if (x + y == -2){break;} else{son[x].push_back(y);son[y].push_back(x);}}cout << hungarian() << endl;repd(i, 1, n){// chu(linker[i]);if (linker[i] != -1){printf("%d %d\n", i, linker[i] );}}return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉載于:https://www.cnblogs.com/qieqiemin/p/11627283.html

總結

以上是生活随笔為你收集整理的洛谷 P2756 飞行员配对方案问题 （二分图/网络流，最佳匹配方案）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。