P2071 座位安排


P2071 座位安排

题目背景
公元二零一四年四月十七日,小明参加了省赛,在一路上,他遇到了许多问题,请你帮他解决。

题目描述
已知车上有N排座位,有N*2个人参加省赛,每排座位只能坐两人,且每个人都有自己想坐的排数,问最多使多少人坐到自己想坐的位置。

输入格式
第一行,一个正整数N。

第二行至第N*2+1行,每行两个正整数Si1,Si2,为每个人想坐的排数。

输出格式
一个非负整数,为最多使得多少人满意。

输入输出样例
输入

4
1 2
1 3
1 2
1 3
1 3
2 4
1 3
2 3

输出

7

说明/提示
对于10%的数据 N≤10
对于30%的数据 N≤50
对于60%的数据 N≤200
对于100%的数据 N≤2000

思路:
像这样有两个不同的集合,问你两集合间最多能有多少匹配的问题。我们都采用最大匹配—二分图。

对于这道题我们如何去变成最大匹配问题呢?(他可是有一排两个座位

我们一般的匈牙利算法的模板如下:

bool find(int x)
{
for(int i=1; i<=m; i++)
{
if(!cover[i] && e[x][i])
{
cover[i]=1;
int q=link[i];
link[i]=x;
if(!q || find(q)) return 1;
link[i]=q;
}
}
return 0;
}

我们想,link[i]表示右图中i能与左图的哪个数相匹配。

那如果我们把右图看成座位,link[i]表示第i排座位与哪两个人匹配。那大家就很容易想出,题目既然规定一排两个座位,那我们就将link数组开成二维的不就行了。

link[i][0]ilink[i][0]表示第i排一号座位与哪个人匹配

link[i][0]表示第i排一号座位与哪个人匹配

link[i][1]ilink[i][1]表示第i排二号座位与哪个人匹配

link[i][1]表示第i排二号座位与哪个人匹配

修改后的匈牙利算法:

bool find(int x)
{
for(int i=hd[x]; i; i=e[i].next)
{
int y=e[i].v; //枚举第几排
if(!cover[y]) //判断是否选过当前排(只对于x这个人)
{
cover[y]=1; //标识(只对于x这个人)
if(!link[y][0] || find(link[y][0])) //表示壹号座位是否能与x匹配
{link[y][0]=x; return 1;}
if(!link[y][1] || find(link[y][1])) //表示二号座位是否能与x匹配
{link[y][1]=x; return 1;}
}
}
return 0;
}

然后我们知道了匈牙利算法怎么做,接着就要考虑怎么建图了。

邻接矩阵的复杂度:O(

n2mn^2m

n2m)
邻接表的复杂度:O(

2n×m2n \times m

2n×m) 好像是吧,请大佬斧正!

所以我们分析完复杂度,便可以知道,邻接矩阵是会T的,便采用邻接表。

code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#define fre(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout);
#define ll long long

using namespace std;

const int MAX=2147483647;
const int N=4e3+10;
struct node {int u, v, next;} e[2*N];
int n, a, b, hd[N], tot, cover[N], link[N][2], ans;

void add(int x,int y) {e[++tot]=(node){x,y,hd[x]}; hd[x]=tot;}

bool find(int x)
{
for(int i=hd[x]; i; i=e[i].next)
{
int y=e[i].v;
if(!cover[y])
{
cover[y]=1;
if(!link[y][0] || find(link[y][0]))
{link[y][0]=x; return 1;}
if(!link[y][1] || find(link[y][1]))
{link[y][1]=x; return 1;}
}
}
return 0;
}

int main()
{
//fre();
scanf("%d",&n);
for(int i=1; i<=2 * n; i++)
{
scanf("%d%d", &a, &b);
add(i, a), add(i, b);
}
for(int i=1; i<=2 * n; i++)
{
memset(cover,0,sizeof(cover));
if(find(i)) ans++;
}
printf("%d", ans);
return 0;
}

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

P2071 座位安排

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » P2071 座位安排
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏