Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

RPWT ^_^

Posted by gaosimeng at 2007-08-14 21:20:00 on Problem 1469
In Reply To:why wa? Posted by:star6 at 2007-08-14 21:17:01
> #include<cstdio>
> #include<algorithm>
> 
> 
> const	int		maxn=301;
> 
> struct	mnode
> {
> 	int		v;
> 	mnode	*next;
> };
> 
> mnode	mem[maxn];
> int		mtail;
> 
> mnode	*graph[maxn];
> int		n,m;
> 
> int		matchy[maxn];
> bool	marked[maxn];
> 
> void	gadd(int	u,int	v)
> {
> 	mtail++;
> 	mem[mtail].v=v;
> 	mem[mtail].next=graph[u];
> 	graph[u]=&mem[mtail];
> }
> void	init()
> {
> 	int		i,t,v;
> 	
> 	mtail=0;
> 	memset(graph,0,sizeof(graph));
> 	scanf("%d %d\n",&n,&m);
> 	memset(matchy,0,sizeof(matchy));
> 	memset(marked,0,sizeof(marked));
> 	
> 	for (i=1;i<=n;i++)
> 	{
> 		scanf("%d",&t);
> 		while (t--)
> 		{
> 			scanf("%d",&v);
> 			gadd(i,v);
> 		}
> 		scanf("\n");
> 	}
> 	
> }
> 
> bool	search(int	v)
> {
> 	mnode		*iter;
> 	
> 	if (marked[v])
> 		return(false);
> 	
> 	marked[v]=true;
> 	for (iter=graph[v];iter;iter=iter->next)
> 		if ((!matchy[iter->v])||(search(matchy[iter->v])))
> 		{
> 			matchy[iter->v]=v;
> 			return(true);
> 		}
> 	return(false);
> }
> void	starmain()
> {
> 	int		i;
> 	
> 	for (i=1;i<=n;i++)
> 	{
> 		memset(marked,0,sizeof(marked));		
> 		if (!search(i))
> 		{
> 			printf("NO\n");
> 			return;
> 		}
> 	}
> 	printf("YES\n");
> 	
> }
> int		main()
> {
> 	int		t;
> 	
> //	freopen("c:\\in.txt","r",stdin);
> 	
> 	scanf("%d\n",&t);
> 	while (t--)
> 	{
> 		init();
> 		starmain();
> 	}
> 	return(0);
> }

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator