哪些招聘网站做海外招聘,新云网站模板,少女免费观看片tv,福田网站建设哪家便宜题干#xff1a;
题目背景
第二次世界大战时期..
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员#xff0c;其中1 名是英国飞行员#xff0c;另1名是外籍飞行员。在众多的飞行员中…题干
题目背景
第二次世界大战时期..
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员其中1 名是英国飞行员另1名是外籍飞行员。在众多的飞行员中每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况试设计一个算法找出最佳飞行员配对方案使皇家空军一次能派出最多的飞机。
对于给定的外籍飞行员与英国飞行员的配合情况编程找出一个最佳飞行员配对方案使皇家空军一次能派出最多的飞机。
输入输出格式
输入格式
第 1 行有 2 个正整数 m 和 n。n 是皇家空军的飞行员总数(n100)m 是外籍飞行员数(mn)。外籍飞行员编号为 1~m英国飞行员编号为 m1~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
题目大意 给一个二分图求最大匹配并且输出方案。
解题报告 直接网络流建图注意边上的流量都是1然后输出方案的时候就看每个左侧顶点连出的边是否流量是0就可以了。流量是0说明有流量流过也就是匹配了这一对点。
题目描述的边的流量设为inf也可以但是这样判断的时候就是要判断反边的流量是否不为0.
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#define F first
#define S second
#define ll long long
#define pb push_back
#define pm make_pair
using namespace std;
typedef pairint,int PII;
const int MAX 2e5 5;
int n,m;
int tot;
struct Edge {int to,ne,w;
} e[100005 * 2];
int head[10005];
int st,ed;
int dis[10050],q[10005];//一共多少个点跑bfsdis数组和q数组就开多大。
void add(int u,int v,int w) {e[tot].tov;e[tot].ww;e[tot].nehead[u];head[u]tot;
}
bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front0,tail0;q[tail]st;dis[st]0;while(fronttail) {int cur q[front];if(cur ed) return 1;front;for(int i head[cur]; i!-1; i e[i].ne) {if(e[i].wdis[e[i].to]0) {q[tail]e[i].to;dis[e[i].to]dis[cur]1;}}}if(dis[ed]-1) return 0;return 1;
}
int dfs(int cur,int limit) {//limit为源点到这个点的路径上的最小边权 if(limit0||cured) return limit;int w,flow0;for(int i head[cur]; i!-1; i e[i].ne) { if(e[i].wdis[e[i].to]dis[cur]1) {wdfs(e[i].to,min(limit,e[i].w));e[i].w-w;e[i^1].ww;floww;limit-w;if(limit0) break;}}if(!flow) dis[cur]-1;return flow;
}
int dinic() {int ans 0;while(bfs(st,ed)) ansdfs(st,0x7fffffff);return ans;
}
int main()
{cinmn;st0;edn1;tot1;for(int i 0; in; i) head[i] -1;for(int i 1; im; i) add(st,i,1),add(i,st,0);for(int i m1; in; i) add(i,ed,1),add(ed,i,0);for(int a,b;; ) {scanf(%d%d,a,b);if(a -1 b -1) break;add(a,b,1);add(b,a,0);}int ans dinic();if(ans 0) puts(No Solution!);else {printf(%d\n,ans); for(int u 1; um; u) {for(int i head[u]; ~i; i e[i].ne) {int v e[i].to;if(v st) continue;if(e[i].w 0) {printf(%d %d\n,u,v);}}}}return 0;
}
