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

第一个二分,1A,16MS,贴代码

Posted by speedcell4 at 2011-08-17 13:21:23 on Problem 1274
#include<iostream>
#define SIZE 201
using namespace std;
int n,m,k,x;
int to[SIZE];
bool v[SIZE],a[SIZE][SIZE];
bool canGo(int x)
{
    for(int i=0;m-i>0;i++)
    {
        if(v[i]==false&&a[x][i]==true)
        {
            v[i]=true;
            if(to[i]==-1||canGo(to[i]))
            {
                to[i]=x;
                return true;
            }
        }
    }
    return false;
}
int MaxMatch(void)
{
    int count=0;
    for(int i=0;n-i>0;i++)
    {
        memset(v,false,sizeof(v));
        if(canGo(i)) count++;
    }
    return count;
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        memset(to,-1,sizeof(to));
        memset(a,false,sizeof(a));
        for(int i=0;n-i>0;i++)
        {
            scanf("%d",&k);
            for(int j=0;k-j>0;j++)
            {
                scanf("%d",&x);
                a[i][x-1]=true;
            }
        }
        printf("%d\n",MaxMatch());
    }
    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