WA

#include<iostream>
#define maxv 505
using namespace std;
bool connected[maxv][maxv];
int pre[maxv],ans,v;
bool used[maxv];
bool dfs(int t)
{
    for(int i=1;i<=v;i++)
    {
        if(connected[t][i] && !used[i])
        {
            used[i]=true;
            if(pre[i]==-1 || dfs(i))
            {
                pre[i]=t;
                return true;
            }
        }
    }
    return false;
}
int match()
{
    ans=0;
    memset(pre,-1,sizeof(pre));
    for(int i=1;i<=v;i++)
    {
        memset(used,0,sizeof(used));
        if(dfs(i))
            ans++;
    }
    return ans;
}
int main()
{
    int a,b,e;
    scanf("%d%d",&v,&e);
    memset(connected,0,sizeof(connected));
    for(int i=1;i<=e;i++)
    {
        scanf("%d%d",&a,&b);
        connected[a][b]=1;
    }
    printf("%d\n",match());
    return 0;
}


AC


#include <iostream>
#include <stdlib.h>
#define MAX 501

using namespace std;

bool used[MAX];
int match[MAX],res;
bool mat[MAX][MAX];

bool passway(int k,int n){//察看第k个点出发能否有增广路经
    int i;
    for(i=1;i<=n;i++)
    {
        if(mat[k][i])
        {//k和i邻接
           if(!used[i])
           {
               used[i] =1;
               if(match[i]==-1 || passway(match[i],n))
               {
                   match[i] = k;
                   return true;
               }
           }
        }
    }
    return false;
}

void hungary(int n)
{
    memset(match,-1,sizeof(match));
   
    for(int i=1;i<=n;i++)
    {
        memset(used,0,sizeof(used));
        if(passway(i,n)) 
            res++;
    }
}

int main(int argc, char *argv[])
{
int i,j,k,n,c,r;
memset(mat,0,sizeof(mat));

scanf("%d%d",&n,&k);

for(i=1;i<=k;i++)
{
      scanf("%d%d",&r,&c);
      mat[r][c] = 1;
}

res = 0;
hungary(n);
printf("%d\n",res);

system("PAUSE");   
return 0;
}

• 哎，原来是一个细节没看到，真是受不了自己 (2146) lizeliang 2009-08-15 14:32:45