[hdu2063]过山车（二分图匹配）

题意：每个女人有感兴趣的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 ;

 }

巴特西

[hdu2063]过山车（二分图匹配）

最新文章

热门文章