poj 1469 COURSES 2 점 일치
2277 단어 poj
학생 수강 신청 문제, 기초 일치 문제.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"); }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ3071: Football(확률 DP)Consider a single-elimination football tournament involving 2n teams, denoted 1, 2, …, 2n. After n rounds, only one team...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.