题意：每个女人有感兴趣的k个男人，过山车两人一组，求最大匹配数。
解题关键：二分图最大匹配。匈牙利算法求解。
1、链式前向星建图
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define maxn 250020
using namespace std;
typedef long long ll;
int n,m,k,a,b;
struct Edge{
int nxt;
int to;
int w;
}e[maxn];
int head[maxn],cnt;
void add_edge(int u,int v){
e[cnt].to=v;
e[cnt].nxt=head[u];
head[u]=cnt++;
}
int pre[maxn];
bool vis[maxn];
bool dfs(int u){
for(int i=head[u];i!=-;i=e[i].nxt){
int v=e[i].to;
if(!vis[v]){
vis[v]=true;
if(pre[v]==-||dfs(pre[v])){
pre[v]=u;
//pre[u]=v;
return true;
}
}
}
return false;
} int hungary(){
int ans=;
memset(pre,-,sizeof pre);
for(int i=;i<=m;i++) {
if(pre[i]==-) {
memset(vis,,sizeof vis);
if(dfs(i)) ans++;
}
}
return ans;
}
int main(){
while(scanf("%d",&k)!=EOF&&k){
memset(head, -, sizeof head);
cnt=;
scanf("%d%d",&m,&n);
for(int i=;i<k;i++){
scanf("%d%d",&a,&b);
add_edge(a,b+m);
}
int ans=hungary();
printf("%d\n",ans);
}
return ;
}
2、邻接矩阵建图
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<cmath>
#define maxn 505
using namespace std;
typedef long long ll;
bool G[maxn][maxn];
int pre[maxn];
bool vis[maxn];
int n,m,k;
bool dfs(int u){
for(int i=;i<=n;i++){
if(G[u][i]&&!vis[i]){
vis[i]=true;
if(pre[i]==-||dfs(pre[i])){
pre[i]=u;
return true;
}
}
}
return false;
} int hungary(){
int num=;
memset(pre,-,sizeof pre);
for(int i=;i<=m;i++){
memset(vis,,sizeof vis);
if(dfs(i)) num++;
}
return num;
}
int main(){
int u,v;
while(scanf("%d",&k)!=EOF&&k){
scanf("%d%d",&m,&n);
memset(G,,sizeof G);
for(int i=;i<k;i++){
scanf("%d%d",&u,&v);
G[u][v]=;
}
int ans=hungary();
printf("%d\n",ans);
}
return ;
}