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

我擦!还是最大匹配的问题!废话不多说ac了再说!

Posted by chenxuan123456789 at 2012-08-10 15:26:29 on Problem 1469
#include<stdio.h>
#include <string.h>
int n,m,num,temp,i,j,sum;
int re[400][400],link[400];
int tag[400];
int DFS(int a)
{
 int ii;
 for(ii=1;ii<=m;ii++)
 {
  if(re[a][ii]!=0&&tag[ii]==0)
  {
   tag[ii]=1;
   if(link[ii]==-1||DFS(link[ii]))
   {
    link[ii]=a;
    return 1;
   }
  }
 }
 return 0;
}
int main()
{
 int ca;
 scanf("%d", &ca);
 while(ca--)
 {
  scanf("%d%d", &n, &m); 
  sum=0;
  memset(re,0,sizeof(re));
  memset(link,-1,sizeof(link));
  for(i=1;i<=n;i++)
  {
   scanf("%d", &num);
   for(j=1;j<=num;j++)
   {
    scanf("%d", &temp);
    re[i][temp]=1;
   }
  }
  for(i=1;i<=n;i++)
  {
   memset(tag,0,sizeof(tag));
   if(DFS(i)==1)
    sum++;
  }
  if(sum==n) 
	  printf("YES\n"); 
  else 
	  printf("NO\n"); 
 }
 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