P2756 飞行员配对方案问题

文章目录

题目背景

第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

题目描述

一共有 n 个飞行员，其中有 m 个外籍飞行员和 (n - m) 个英国飞行员，外籍飞行员从 1 到 m
编号，英国飞行员从 m + 1 到 n 编号。
对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 m 和飞行员总数 n。 从第二行起到倒数第二行，每行有两个整数 u,v，代表外籍飞行员 u 可以和英国飞行员 v 配合。 输入的最后一行保证为 -1，代表输入结束。

输出格式

本题存在 Special Judge。 请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是k。 第 2 行到第 k+1 行，每行输出两个整数
u,v，代表在你给出的方案中，外籍飞行员 u 和英国飞行员 v 配合。这 k 行的 u 与 v 应该互不相同。

输入输出样例
输入 #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

说明/提示

【数据范围与约定】

对于 100% 的数据，保证1≤m≤n<100，1≤u≤m<v≤n，同一组配对关系只会给出一次。 【提示】

请注意输入的第一行先读入 m，再读入 n。

题解：

欢迎开始我们的网络流24题
根据题意我们可以知道这是一个二分图，其实是一个二分图最大匹配的问题，对于二分图我们用网络流的方式来解决
二分图有A和B两个大集合，A和B之间有线，A和B自身内部无线，相当于A和B分别都在自己的层数。我们在创立一个源点s，再创一个终点t，s指向A中所有点，B中所有点指向t，边的流量我们设为1，这样不就构成一个网络流问题

以上说的是对于二分图最大匹配通用解法，具体针对本题
我们先构建从S到A的边，再构建从B到T的边，然后读入数据，
我们在读入时，外籍飞行员是u，英国飞行员的编号为v+n
最后我们输出时还要输出所匹配的结果，因此我们用到一个数组ansk[i]：标号为i的外籍飞行员与标号为ansk[i]-n的英雄飞行员对应
pre用来存在一条增广路中，节点的前一个节点和与之相连的边
其他的都是正常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];//标号为i的外籍飞行员和标号为ansk[i]-n的英国飞行员对应 
struct P{
   
    int fa;//前节点 
    int edge;
}pre[1010];//在一条增广路中，节点的前一个节点和与之相连的边 
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);//构建从B到t 
		addedge(t,i+n,0);//使所有英国空军和汇点相连 
	}

    for(i=1;i<=m;i++)
	{
   
		addedge(s,i,1);//构建从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);//读入数据 
	    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;
}