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数组开成二维的不就行了。
l i n k [ i ] [ 0 ] 表 示 第 i 排 一 号 座 位 与 哪 个 人 匹 配 link[i][0]表示第i排一号座位与哪个人匹配 link[i][0]表示第i排一号座位与哪个人匹配
l i n k [ i ] [ 1 ] 表 示 第 i 排 二 号 座 位 与 哪 个 人 匹 配 link[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（ n 2 m n^2m n2m）
邻接表的复杂度：O（ 2 n × m 2n \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;
}