题目背景
题目 公元二零一四年四月十七日，小明参加了省赛，在一路上，他遇到了许多问题，请你帮他解决。
题目描述
已知车上有
N
N
N排座位，有
N
∗
2
N*2
N∗2个人参加省赛，每排座位只能坐两人，且每个人都有自己想坐的排数，问最多使多少人坐到自己想坐的位置。
输入格式
第一行，一个正整数
Ｎ
Ｎ
Ｎ。
第二行至第
Ｎ
∗
2
+
1
Ｎ*2+1
Ｎ∗2+1行，每行两个正整数
S
i
1
Si1
Si1，
S
i
2
Si2
Si2，为每个人想坐的排数。
输出格式
一个非负整数，为最多使得多少人满意。
输入输出样例
输入 #1
4
1 2
1 3
1 2
1 3
1 3
2 4
1 3
2 3
输出 #1
7
分析：
一句话题解：把最大匹配的连接数组开成分别能分别存储
1
1
1号座位与
2
2
2号座位匹配哪个人即可…… 你要是会网络流那没事了
也就是在模板里改一下：
1
1
1号座位：
if(!link
[qwq
].fir
||find(link
[qwq
].fir
))
{
link
[qwq
].fir
=x
;
return 1;
}
2
2
2号座位：
if(!link
[qwq
].sec
||find(link
[qwq
].sec
))
{
link
[qwq
].sec
=x
;
return 1;
}
CODE：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std
;
const int N
=4e3+10;
struct node
{int to
,next
;}edge
[2*N
];
struct peo
{int fir
,sec
;}link
[N
];
int n
,a
,b
,head
[N
],tot
,cover
[N
],ans
;
void add(int x
,int y
){edge
[++tot
]=(node
){y
,head
[x
]};head
[x
]=tot
;}
bool find(int x
)
{
for(int i
=head
[x
];i
;i
=edge
[i
].next
)
{
int qwq
=edge
[i
].to
;
if(!cover
[qwq
])
{
cover
[qwq
]=1;
if(!link
[qwq
].fir
||find(link
[qwq
].fir
))
{
link
[qwq
].fir
=x
;
return 1;
}
if(!link
[qwq
].sec
||find(link
[qwq
].sec
))
{
link
[qwq
].sec
=x
;
return 1;
}
}
}
return 0;
}
int main()
{
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;
}
