打卡信奥刷题（2541）用C++实现信奥 P2071 座位安排

P2071 座位安排

题目背景

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

题目描述

已知车上有NNN排座位，有2N2N2N个人参加省赛，每排座位只能坐两人，且每个人都有自己想坐的排数，问最多使多少人坐到自己想坐的位置。

输入格式

第一行，一个正整数NNN。

第二行至第2N+12N+12N+1行，每行两个正整数Si,1,Si,2S_{i, 1},S_{i, 2}Si,1​,Si,2​，为每个人想坐的排数。

输出格式

一个非负整数，为最多使得多少人满意。

输入输出样例 #1

输入 #1

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

输出 #1

7

说明/提示

对于10%10\%10%的数据，n≤10n \le 10n≤10；

对于30%30\%30%的数据，n≤50n \le 50n≤50；

对于60%60\%60%的数据，n≤200n \le 200n≤200；

对于100%100\%100%的数据，n≤2000n \le 2000n≤2000。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=5100;intlink[N],cnt[N],w[N][N];boolused[N];intans,n;intx,y;boolfind(intx){for(inti=1;i<=cnt[x];i++){if(!used[w[x][i]]){used[w[x][i]]=true;if(!link[w[x][i]]||find(link[w[x][i]])){link[w[x][i]]=x;returntrue;}}}returnfalse;}voidxyl(){for(inti=1;i<=n*2;i++){memset(used,0,sizeof(used));if(find(i))ans++;}}intmain(){cin>>n;for(inti=1;i<=n*2;i++){cin>>x>>y;w[i][++cnt[i]]=x;w[i][++cnt[i]]=x+n;w[i][++cnt[i]]=y;w[i][++cnt[i]]=y+n;}xyl();cout<<ans;return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容