学步园

邻接矩阵超时，只能用邻接表，注意范围

#include<stdio.h>
#include<string.h>
const int nv=1001;
const int ne=10001;

struct maxmatch{
	int n,size;
	int head[nv];
	int mark[nv];
	int aug[nv];

	struct edge
	{
		int v,w,next;
		edge(){}
		edge(int v,int next,int w):v(v),next(next),w(w){}
	}e[ne];

	inline void init(int nx)
	{
		n=nx;size=0;
		for(int i=1;i<=n;i++)
			head[i]=-1;
	}
	inline void insert(int u,int v,int w=0)
	{
		e[size]=edge(v,head[u],w);
		head[u]=size++;
	}
	inline int  hunt(int n)
	{
		int match=0;
		memset(aug,-1,sizeof(aug));
		for(int i=1;i<=n;i++)
		{
			if(aug[i]==-1)
			{
				memset(mark,0,sizeof(mark));
				match+=find(i);
			}
		}
		return match;
	}
	inline int find(int u)
	{
		for(int i=head[u];i!=-1;i=e[i].next)
		{
			int v=e[i].v;
			if(!mark[v])
			{
				mark[v]=1;
				if(aug[v]==-1||find(aug[v]))
				{
					aug[u]=v;aug[v]=u;
					return 1;
				}
			}
		}
		return 0;
	}
}g;
int main()
{
	int k,n,m,a,b;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&n,&m);
		g.init(2*n);
		while(m--)
		{
			scanf("%d%d",&a,&b);
			g.insert(a,b+n);
		}
		printf("%d\n",g.hunt(n));
	}
	return 0;
}        

另一种简单的

 
#include<stdio.h>
#include<string.h>
#define max 10120
struct edge
{
	int a,next;
}edges[max];
int head[505],k,n,m,matc,flag[505],match[505];
 int Find(int u) 
 {
        for (int i = head[u]; i != -1; i = edges[i].next) 
	{
		int v = edges[i].a;
                if(!flag[v])
		{
                    flag[v] = 1;
                    if (match[v] == -1 || Find(match[v])) 
		    {
                          match[v] = u;
                          return 1;
                    }
                }
        }
        return 0;
 }
 void matchs() 
 {
        matc = 0;
        for (int i = 1; i <= n; i++) 
	{ 
	    memset(flag, 0, sizeof(flag));
            if (Find(i)) 
            //不用剪枝时间更短
	    {
                matc ++ ;
            }
        }
 }
 
int main()
{
	int a,b;
	scanf("%d",&k);
	while(k--)
	{
		scanf("%d%d",&n,&m);
		memset(head,-1,sizeof(head));
		memset(match, -1, sizeof(match));
		int num=1;
		for(int i=1;i<=m;i++)
		{
			scanf("%d%d",&a,&b);
			edges[num].a=b;
			edges[num].next=head[a];
			head[a]=num++;
                  //注意邻接表的使用		
                }
		matchs();
		printf("%d\n",matc);
	}
	return 0;
}