HDU 2063 过山车

题上要求找一个二分图最大匹配;

[cpp]
/****************************
HDU 2063
By: South_stream
Email: South_stream@163.com
****************************/

#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: South_stream@163.com
****************************/

#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;
补充：软件开发 , C++ ,