acwing-2175. 飞行员配对方案问题(二分图|最大流)「建议收藏」

acwing-2175. 飞行员配对方案问题(二分图|最大流)「建议收藏」第二次世界大战时期,英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 2 名飞行员,其中 1 名是英国飞行员,另 1 名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。输入格式第 1 行有 2 个正整数 m 和 n。m 是外籍飞行员数;

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

第二次世界大战时期,英国皇家空军从沦陷国征募了大量外籍飞行员。

由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的 2 名飞行员,其中 1 名是英国飞行员,另 1 名是外籍飞行员。

在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

如何选择配对飞行的飞行员才能使一次派出最多的飞机。

对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。

输入格式
第 1 行有 2 个正整数 m 和 n。m 是外籍飞行员数;n 是皇家空军的飞行员总数。

外籍飞行员编号为 1∼m;英国飞行员编号为 m+1∼n。

接下来每行有 2 个正整数 i 和 j,表示外籍飞行员 i 可以和英国飞行员 j 配合。

文件最后以 2 个 −1 结束。

输出格式
第 1 行是最佳飞行员配对方案一次能派出的最多的飞机数 M。

接下来 M 行是最佳飞行员配对方案。

每行有 2 个正整数 i 和 j,表示在最佳飞行员配对方案中,外籍飞行员 i 和英国飞行员 j 配对。

如果有多种配对方案,则输出任意一种即可,方案内部配对输出顺序随意。

数据范围
1<m<n<100

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

题解
二分图,匈牙利算法,时间复杂度O(nm)

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e2 + 10;
int match[N],vis[N];
int g[N][N];
bool find(int x){ 
   
    for(int i = 1;i <= n;i ++){ 
   
        if(vis[i] || !g[x][i])continue;
        vis[i] = true;
        if(!match[i] || find(match[i])){ 
   
            match[i] = x;
            return true;
        }
    }
    return false;
}
int main(){ 
   
    cin>>m>>n;
    int x,y;
    while(cin>>x>>y,x != -1 && y != -1){ 
   
        g[x][y - m] = 1;
    }
    int res = 0;
    for(int i = 1;i <= n;i ++){ 
   
        memset(vis,0,sizeof vis);
        if(find(i))res ++;
    }
    cout<<res<<endl;
    for(int i = 1;i <= n - m;i ++){ 
   
        if(match[i])cout<<match[i]<<" "<<i + m<<endl;
    }
    return 0;
}

2 题解
最大流

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
const int M = 1e5 + 10;
const int INF = 0x3f3f3f3f;
struct Edge{ 
   
    int v,next,w;
}edge[M];
int head[N],cnt;
int n,m,s,e;
void add(int u,int v,int w){ 
   
    edge[cnt].v = v;
    edge[cnt].w = w;
    edge[cnt].next = head[u];
    head[u] = cnt ++;
}
int q[N],hh = 0,tt = 0;
int d[N],cur[N];
bool bfs(){ 
   
    tt = hh = 0;
    memset(d,-1,sizeof d);
    q[tt ++] = s,d[s] = 0,cur[s] = head[s];
    while(hh < tt){ 
   
        int t = q[hh ++];
        for(int i = head[t];~i;i = edge[i].next){ 
   
            int v = edge[i].v,w = edge[i].w;
            if(d[v] == -1 && w > 0){ 
   
                d[v] = d[t] + 1;
                cur[v] = head[v];
                if(v == e)return true;
                q[tt ++] = v;
            }
        }
    }
    return false;
}
int dfs(int u,int limit){ 
   
    if(u == e)return limit;
    int flow = 0;
    for(int i = cur[u];~i && flow < limit;i = edge[i].next){ 
   
        int v = edge[i].v,w = edge[i].w;
        cur[u] = i;
        if(d[v] == d[u] + 1 && w > 0){ 
   
            int t = dfs(v,min(limit - flow,w));
            if(!t)d[v] = -1;
            flow += t,edge[i].w -= t,edge[i ^ 1].w += t;
        }
    }
    return flow;
}
int dinic(){ 
   
    int maxflow = 0,flow = 0;
    while(bfs())
        while(flow = dfs(s,INF))maxflow += flow;
    return maxflow;
}
int main(){ 
   
    memset(head,-1,sizeof head);
    cin>>m>>n;
    s = 0,e = n + 1;
    for(int i = 1;i <= m;i ++)add(0,i,1),add(i,0,0);
    for(int i = m + 1;i <= n;i ++)add(i,n + 1,1),add(n + 1,i,0);
    int x,y;
    while(cin>>x>>y,x != -1 && y != -1){ 
   
        add(x,y,1);
        add(y,x,0);
    }
    cout<<dinic()<<endl;
    for(int i = 0;i < cnt;i += 2){ 
   
        if(edge[i].w == 0 && edge[i].v > m && edge[i].v < n + 1){ 
   
            cout<<edge[i ^ 1].v<<" "<<edge[i].v<<endl;
        }
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168593.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • spdlog用法

    spdlog用法转自:https://blog.csdn.net/haojie_superstar/article/details/89383433?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-19.control&dist_request_id=1328730.643.16167433128441371&depth_1-utm_source=distribute.pc_relevant.none-task-bl

  • HTML网页调用 网易云 音乐播放器代码

    HTML网页调用 网易云 音乐播放器代码表现形式一:单曲播放调用代码:&amp;lt;iframeframeborder=&quot;no&quot;border=&quot;0&quot;marginwidth=&quot;0&quot;marginheight=&quot;0&quot;width=100%height=86src=&quot;http://music.163.com/outchain/player?type=2&am

  • 数学建模之MATLAB画图汇总

    1.二维数据曲线图1.1绘制二维曲线的基本函数1.plot()函数plot函数用于绘制二维平面上的线性坐标曲线图,要提供一组x坐标和对应的y坐标,可以绘制分别以x和y为横、纵坐标的二维曲线。例:t=0:0.1:2*pi;x=2*t;y=t.*sin(t).*sin(t);plot(x,y);2.含多个输入参数的plot函数plot函数…

  • 卡巴斯基硬件虚拟化保护_ilab实验室

    卡巴斯基硬件虚拟化保护_ilab实验室原文:https://securelist.com/iot-lottery/83300/本文由看雪翻译小组南极小虾编译黑色星期五和网络星期一是购物的好机会。市场上充斥着各种各样的商品,包括许多令人兴奋的智能设备,让我们的生活更便捷、更舒适。作为一狂热的剁手族,在卡巴斯基实验室的安全研究人员也和其他人一样对新鲜事物充满好奇。但我们也对众多物联网设备保留了一份质疑,即使在价格合适的情

  • 密码学专题 SSL协议

    密码学专题 SSL协议SSL协议为不同的高层协议(http、FTP)提供安全服务 SSL握手协议、SSL修改密文协议和SSL告警协议的目的是为了管理和SSL相关的密文交换 连接:两台主机之间提供特定类型的数据传输,是点对点的关系;连接是短暂的,每一个连接都会和一个会话相互关联 会话:是指客户和服务器之间的关联,会话是通过握手协议创建的;会话是加密安全参数的一个集合,包含加密算法、临时的加密密钥等信息;会话可以为多个连接所共享,就可以避免为每个连接建立都要进行安全参数的协商带来的昂贵的时间代价。如果服务器和客户端之..

  • 使用SurfaceView和MediaPlayer实现视频做为背景

    使用SurfaceView和MediaPlayer实现视频做为背景

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号