LuoguP2756 飞行员配对方案问题(最大流)
2024-08-31 16:23:59
题目背景
第二次世界大战时期..
题目描述
英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的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!’。
解题思路:
这个显然是二分图最大匹配,最后要输出方案还是写最大流吧。
最大流解决二分图最大匹配问题,建一个源点,建一个汇点,
源点与前N个点连$∞$,后M个与汇点连$∞$,中间建1的边。
最大流就是最大匹配。
代码:
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
const int oo=0x3f3f3f3f;
struct pnt{
int hd;
int lyr;
int now;
}p[];
struct ent{
int twd;
int lst;
int vls;
}e[];
int n,m;
int s,t;
int cnt;
std::queue<int>Q;
void ade(int f,int t,int v)
{
cnt++;
e[cnt].twd=t;
e[cnt].vls=v;
e[cnt].lst=p[f].hd;
p[f].hd=cnt;
return ;
}
bool Bfs(void)
{
while(!Q.empty())
Q.pop();
for(int i=;i<=n+m+;i++)
p[i].lyr=;
p[s].lyr=;
Q.push(s);
while(!Q.empty())
{
int x=Q.front();
Q.pop();
for(int i=p[x].hd;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].lyr==&&e[i].vls>)
{
p[to].lyr=p[x].lyr+;
if(to==t)
return true;
Q.push(to);
}
}
}
return false;
}
int Dfs(int x,int fll)
{
if(x==t)
return fll;
for(int &i=p[x].now;i;i=e[i].lst)
{
int to=e[i].twd;
if(p[to].lyr==p[x].lyr+&&e[i].vls>)
{
int ans=Dfs(to,std::min(fll,e[i].vls));
if(ans>)
{
e[i].vls-=ans;
e[((i-)^)+].vls+=ans;
return ans;
}
}
}
return ;
}
int Dinic(void)
{
int ans=;
while(Bfs())
{
for(int i=;i<=n+m+;i++)
p[i].now=p[i].hd;
int dlt;
while(dlt=Dfs(s,oo))
ans+=dlt;
}
return ans;
}
int main()
{
//freopen("a.in","r",stdin);
scanf("%d%d",&n,&m);
s=n+m+,t=s+;
for(int i=;i<=n;i++)ade(s,i,),ade(i,s,);
for(int i=;i<=m;i++)ade(i+n,t,),ade(t,i+n,);
while(true)
{
int a,b;
scanf("%d%d",&a,&b);
if(a==-&&b==-)
break;
ade(a,b,);
ade(b,a,);
}
int ans=Dinic();
if(ans)
{
printf("%d\n",ans);
for(int i=;i<=n;i++)
{
for(int j=p[i].hd;j;j=e[j].lst)
{
int to=e[j].twd;
if(e[j].vls==&&to>n&&to<=n+m)
{
printf("%d %d\n",i,to);
}
}
}
}else
puts("No Solution!");
return ;
}
最新文章
- $_SERVER
- Maven和Gradle对比
- 什么情况下会用到try-catch
- SSIS自定义数据流组件开发(血路)
- push to deploy
- laravel 删除一条migration后要执行composer命令
- Android的ADT内容助手快捷方式设置
- QDomDocument Access violation writing location
- ubuntu 安装 flash player
- 从Ecipse中导出程序至apk
- Spring Jdbc使用like模糊查询
- hadoop参数配置
- 提高java编程质量 - (一)易变业务使用脚本语言编写
- YARN作业运行机制
- Javascript 内核Bug
- NGINX详解
- VGG
- GDAL——命令使用专题——ogrinfo命令
- 多线程-Callable、Future、FutureTask
- 【Python】【辅助程序】练手小程序:记录外网动态IP地址