poj 1469 COURSES 2 점 일치

2277 단어 poj
http://poj.org/problem?id=1469
학생 수강 신청 문제, 기초 일치 문제.p 교시 수업 이 있 고 n 명의 학생 이 있 으 며 매 교시 수업 은 지 정 된 몇 명의 학생 이 참가 할 수 있 지만 모든 학생 은 한 시간 만 참가 할 수 있 습 니 다.지금 몇 명의 학생 들 을 찾 아서 그들 을 만 들 수 있 느 냐 고 묻는다. 1. 모든 학생 들 이 서로 다른 수업 과 일치한다. 2. 매 수업 마다 한 학생 과 일치한다.매 칭 수가 과정 수 와 같 는 지 최대 매 칭 을 구 하 는 것 이다.똑 같 으 면 요 구 를 만족 시 킬 수 있 잖 아. Source Code
 #include<stdio.h>   #include<stdlib.h>   #include<string.h>      int nx, ny;             // X    、Y        int mx[302], my[102];   // X       、Y           bool vy[102];           //   Graph Traversal         bool adj[302][102];     //     adjacency matrix       //  DFS           bool DFS(int x)    {        for (int y=0; y<ny; ++y)            if (adj[x][y] && !vy[y])            {                vy[y] = true;                   //                         if (my[y] == -1 || DFS(my[y]))                {                   mx[x] = y; my[y] = x;                   return true;                   }            }        return false;    }       int bipartite_matching()    {        //             。        memset(mx, -1, sizeof(mx));           memset(my, -1, sizeof(my));           //    X               ,        //          。        int c = 0;        for (int x=0; x<nx; ++x)   //     if (mx[x] == -1)    // x     ,     。            {                //   Graph Traversal                memset(vy, false, sizeof(vy));                if (DFS(x)) c++;            }        return c;    }   main()   {            int t,a,b,i,n,c,ans;            scanf("%d",&t);            while(t--)            {               memset(adj,0, sizeof(adj));               scanf("%d%d",&a,&b);               for(i=0;i<a;i++)               {                 scanf("%d",&n);                 while(n--)                 {                    scanf("%d",&c);                    adj[c-1][i]=1;                 }               }               nx=b;ny=a;               ans=bipartite_matching();               if(ans==a)               printf("YES
"); else printf("NO
"); } system("pause"); }

좋은 웹페이지 즐겨찾기