飞行员配对方案问题
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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!’。
输入样例
5 10 1 7 1 8 2 6 2 9 2 10 3 7 3 8 4 7 4 8 5 10 -1 -1输出样例
4 1 7 2 9 3 8 5 10二分图最大匹配
#include <bits/stdc++.h> using namespace std; const int maxn=30000; struct node{ int v,next; }e[maxn]; int match[maxn],dismatch[maxn],vis[maxn],t,head[maxn],ans,m,n,u,v; void add(int u,int v){ t++; e[t].v=v; e[t].next=head[u]; head[u]=t; } bool dfs(int u) { for (int i = head[u]; i; i = e[i].next) { int v = e[i].v; if (!vis[v]) { vis[v] = 1; if (!match[v] || dfs(match[v])) { match[v] = u; dismatch[u]=v; return 1; } } } return 0; } int main(){ scanf("%d%d",&n,&m); while (scanf("%d%d",&u,&v)){ if (u==-1&&v==-1){ break; } add(u,v); } for (int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if (dfs(i)){ ans++; } } if (ans){ printf("%d\n",ans); for (int i=1;i<=m;i++){ if (dismatch[i]){ printf("%d %d\n",i,dismatch[i]); } } }else{ printf("No Solution!\n"); } }网络流建图
超级源点S与1~m连流量为1的边，m+1~n与超级汇点T连流量为1的边，所给的边，连流量为0x3f3f3f3f
#include <bits/stdc++.h> using namespace std; const int maxn=1e5+7; const int maxm=1e5+7; const int inf=0x3f3f3f3f; int n,m,u,v; struct Dinic { struct Edge { int next, f, to; } e[maxm]; int head[maxn], dep[maxn], tol, ans; int cur[maxn]; int src, sink, n; void add(int u, int v, int f) { tol++; e[tol].to = v; e[tol].next = head[u]; e[tol].f = f; head[u] = tol; tol++; e[tol].to = u; e[tol].next = head[v]; e[tol].f = 0; head[v] = tol; } bool bfs() { queue<int> q; memset(dep, -1, sizeof(dep)); q.push(src); dep[src] = 0; while (!q.empty()) { int now = q.front(); q.pop(); for (int i = head[now]; i; i = e[i].next) { if (dep[e[i].to] == -1 && e[i].f) { dep[e[i].to] = dep[now] + 1; if (e[i].to == sink) return true; q.push(e[i].to); } } } return false; } int dfs(int x, int maxx) { if (x == sink) return maxx; for (int &i = cur[x]; i; i = e[i].next) { if (dep[e[i].to] == dep[x] + 1 && e[i].f > 0) { int flow = dfs(e[i].to, min(maxx, e[i].f)); if (flow) { e[i].f -= flow; e[i ^ 1].f += flow; return flow; } } } return 0; } int dinic(int s, int t) { ans = 0; this->src = s; this->sink = t; while (bfs()) { for (int i = 0; i <= n; i++) cur[i] = head[i]; while (int d = dfs(src, inf)) ans += d; } return ans; } void init(int n) { this->n = n; memset(head, 0, sizeof(head)); tol = 1; } } G; int main(){ scanf("%d%d",&m,&n); G.init(n+1+m); while (scanf("%d%d",&u,&v)){ if (u==-1&&v==-1){ break; } G.add(u,v,inf); } for (int i=1;i<=m;i++){ G.add(0,i,1); } for (int i=m+1;i<=m+n;i++){ G.add(i,n+m+1,1); } int ans=G.dinic(0,n+m+1); if (ans){ printf("%d\n",ans); }else{ printf("No Solution!\n"); } }太空飞行计划问题
题目描述
W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1，E2，…，Em}，和进行这些实验需要使用的全部仪器的集合I={I1，I2，…In}。实验Ej需要用到的仪器是I的子集RjÍI。配置仪器Ik的费用为ck美元。实验Ej的赞助商已同意为该实验结果支付pj美元。W教授的任务是找出一个有效算法，确定在一次太空飞行中要进行哪些实验并因此而配置哪些仪器才能使太空飞行的净收益最大。这里净收益是指进行实验所获得的全部收入与配置仪器的全部费用的差额。
对于给定的实验和仪器配置情况，编程找出净收益最大的试验计划。
输入格式
第1行有2 个正整数m和n。m是实验数，n是仪器数。接下来的m 行，每行是一个实验的有关数据。第一个数赞助商同意支付该实验的费用；接着是该实验需要用到的若干仪器的编号。最后一行的n个数是配置每个仪器的费用。
输出格式
第1 行是实验编号；第2行是仪器编号；最后一行是净收益。
输入样例
2 3 10 1 2 25 2 3 5 6 7输出样例
1 2 1 2 3 17
原文：https://www.cnblogs.com/Accpted/p/11298565.html