HDU 2063 過山車

題上要求找一個二分圖最大匹配;

[cpp]
/****************************
HDU 2063
By: South_stream
Email: [email protected]
****************************/ 
 
#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
#include<queue>  
#define sf scanf  
#define pf printf  
#define cls(a) memset(a,0,sizeof(a))  
#define _cls(a) memset(a,-1,sizeof(a))  
 
using namespace std; 
const int Maxn=20010; 
const int Inf=1<<30; 
struct Edge_t{ 
    int to,next; 
}edge[2010]; 
int head[1010]; 
int et; 
int n,m;///n是matchx的個數,m是matchy的個數  
int match[1010]; 
int matchx[1010],matchy[1010];///匹配x,匹配y  
int dx[1010],dy[1010];///增廣路時路徑  
 
inline void adde(int u,int v){ 
    edge[et].to=v,edge[et].next=head[u],head[u]=et++; 
    edge[et].to=u,edge[et].next=head[v],head[v]=et++; 
} 
 
bool searchp(){///增廣路  
    int i,j,h=0,t=-1,u,v,e; 
    cls(dx),cls(dy); 
    int dq[1010],dis=Inf; 
    for(i=1;i<=n;i++)///多條增廣路一起找  
        if(matchx[i]<0) dq[++t]=i,dx[i]=0; 
    while(h<=t){ 
        u=dq[h++]; 
        for(e=head[u];e!=-1;e=edge[e].next){ 
            v=edge[e].to; 
            if(dy[v]) continue; 
            dy[v]=dx[u]+1; 
            if(matchy[v]<0) dis=dy[v]; 
            else{ 
                dx[matchy[v]]=dy[v]+1; 
                dq[++t]=matchy[v]; 
            } 
        } 
    } 
    return dis!=Inf;///是否找到新的增廣路  
} 
 
bool dfs(int index){ 
    int v,e; 
    for(e=head[index];e!=-1;e=edge[e].next){ 
        v=edge[e].to; 
        if(dy[v]==dx[index]+1){ 
            dy[v]=-1; 
            if(matchy[v]<0 || dfs(matchy[v])){ 
                matchx[index]=v; 
                matchy[v]=index; 
                return true; 
            } 
        } 
    } 
    return false; 
} 
 
int hkbg(){///HopcroftKarp binary graphz  
    int ret=0,i; 
    _cls(matchx),_cls(matchy); 
    while(searchp()){ 
        for(i=1;i<=n;i++) 
            if(matchx[i]<0) 
                ret+=dfs(i); 
    } 
    return ret; 
} 
 
int main(){ 
    int k,u,v; 
    while(sf("%d",&k),k){ 
        sf("%d%d",&n,&m); 
        _cls(head),et=0; 
        while(k--){ 
            sf("%d%d",&u,&v); 
            adde(u,v+n); 
        } 
        pf("%d\n",hkbg()); 
    } 
    return 0; 
} 

/****************************
HDU 2063
By: South_stream
Email: [email protected]
****************************/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define sf scanf
#define pf printf
#define cls(a) memset(a,0,sizeof(a))
#define _cls(a) memset(a,-1,sizeof(a))

using namespace std;
const int Maxn=20010;
const int Inf=1<<30;
struct Edge_t{
 int to,next;
}edge[2010];
int head[1010];
int et;
int n,m;///n是matchx的個數,m是matchy的個數
int match[1010];
int matchx[1010],matchy[1010];///匹配x,匹配y
int dx[1010],dy[1010];///增廣路時路徑

inline void adde(int u,int v){
 edge[et].to=v,edge[et].next=head[u],head[u]=et++;
 edge[et].to=u,edge[et].next=head[v],head[v]=et++;
}

bool searchp(){///增廣路
 int i,j,h=0,t=-1,u,v,e;
 cls(dx),cls(dy);
 int dq[1010],dis=Inf;
 for(i=1;i<=n;i++)///多條增廣路一起找
  if(matchx[i]<0) dq[++t]=i,dx[i]=0;
 while(h<=t){
  u=dq[h++];
  for(e=head[u];e!=-1;e=edge[e].next){
   v=edge[e].to;
   if(dy[v]) continue;
   dy[v]=dx[u]+1;
   if(matchy[v]<0) dis=dy[v];
   else{
    dx[matchy[v]]=dy[v]+1;
    dq[++t]=matchy[v];
   }
  }
 }
 return dis!=Inf;///是否找到新的增廣路
}

bool dfs(int index){
 int v,e;
 for(e=head[index];e!=-1;e=edge[e].next){
  v=edge[e].to;
  if(dy[v]==dx[index]+1){
   dy[v]=-1;
   if(matchy[v]<0 || dfs(matchy[v])){
    matchx[index]=v;
    matchy[v]=index;
    return true;
   }
  }
 }
 return false;
}

int hkbg(){///HopcroftKarp binary graphz
 int ret=0,i;
 _cls(matchx),_cls(matchy);
 while(searchp()){
  for(i=1;i<=n;i++)
   if(matchx[i]<0)
    ret+=dfs(i);
 }
 return ret;
}

int main(){
 int k,u,v;
 while(sf("%d",&k),k){
  sf("%d%d",&n,&m);
  _cls(head),et=0;
  while(k--){
   sf("%d%d",&u,&v);
   adde(u,v+n);
  }
  pf("%d\n",hkbg());
 }
 return 0;
}