hdu 1083 Courses(二分图最大匹配)

题意:

P门课,N个学生。      (1<=P<=100    1<=N<=300)

每门课有若干个学生可以成为这门课的代表(即候选人)。

又规定每个学生最多只能成为一门课的代表(即要专一)。

问是否存在一种安排方案使得每门课都有代表。

思路:

二分图最大匹配经典,,看代码。

代码:

int T,n,p;
vector<int> graph[505];
bool bmask[505];
int cx[505],cy[505]; int findPath(int u){
int L=graph[u].size();
rep(i,0,L-1){
int v=graph[u][i];
if(!bmask[v]){
bmask[v]=true;
if(cy[v]==-1||findPath(cy[v])){
cy[v]=u;
cx[u]=v;
return 1;
}
}
}
return 0;
}
int MaxMatch(){
int ans=0;
rep(i,1,p) cx[i]=-1;
rep(i,1,n) cy[i]=-1;
rep(i,1,p) if(cx[i]==-1){
mem(bmask,false);
ans+=findPath(i);
}
return ans;
}
int main(){
cin>>T;
while(T--){
scanf("%d%d",&p,&n);
rep(i,1,p) graph[i].clear(); //p kinds of class
rep(i,1,p){
int x,a;
scanf("%d",&x); //student num
while(x--){
scanf("%d",&a);
graph[i].push_back(a);
}
}
int dd=MaxMatch();
if(dd!=p)
puts("NO");
else
puts("YES");
}
}
上一篇:HUD——1083 Courses


下一篇:hdu 1083 Courses (最大匹配)