P2071 座位安排

題目背景
公元二零一四年四月十七日，小明參加了省賽，在一路上，他遇到了許多問題，請你幫他解決。

題目描述
已知車上有N排座位，有N*2個人參加省賽，每排座位只能坐兩人，且每個人都有自己想坐的排數，問最多使多少人坐到自己想坐的位置。

輸入格式
第一行，一個正整數Ｎ。

第二行至第Ｎ*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]表示第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（$n^{2}m$）
鄰接表的復雜度：O（$2n\times 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 longusing 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; }

總結

以上是生活随笔為你收集整理的P2071 座位安排的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。