HDU 1083 Courses 匹配
标准的匹配问题，直接上代码，有详细的注释
题目地址：
[cpp]
#include <iostream>
using namespace std;
int nx, ny; //X和Y 集合中顶点的个数
int g[305][305]; //邻接矩阵，g[i][j]为1 表示Xi 和Yj 有边相连
int cx[305], cy[305];
int mk[305] ;
int path( int u )
{
for( int v=1 ; v<=ny ; v++ ) //考虑所有Yi 顶点v
{
if( g[u][v] && !mk[v] ) //v 与u 邻接，且没有访问过
{
mk[v]=1; //访问v
//如果v 没有匹配，或者v 已经匹配了，但从cy[v]出发可以找到一条增广路
//注意如果前一个条件成立，则不会递归调用
if( cy[v]==-1||path( cy[v] ) )
{
cx[u]=v; //把v 匹配给u
cy[v]=u; //把u 匹配给v
return 1; //找到可增广路
}
}
}
return 0 ; //如果不存在从u 出发的增广路
}
int MaxMatch( ) //求二部图最大匹配的匈牙利算法
{
int res=0; //所求得的最大匹配
memset(cx,0xff,sizeof(cx)); //从0 匹配开始增广,将cx 和cy 各元素初始化为-1
memset( cy, 0xff, sizeof(cy) );
for( int i=1; i<=nx; i++ )
{
if( cx[i]==-1 ) //从每个未盖点出发进行寻找增广路
{
memset( mk, 0, sizeof(mk) ) ;
res+=path(i); //每找到一条增广路，可使得匹配数加1
}
}
return res;
}
int main()
{
int i,j,T,p,n,max;
cin>>T;
while(T--)
{
memset(g,0,sizeof(g));
cin>>nx>>ny;
for(i=1;i<=nx;i++)
{
cin>>p;
for(j=1;j<=p;j++)
{
cin>>n;
g[i][n]=1;
}
}
max=MaxMatch();
if(max>=nx)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 520;
}
#include <iostream>
using namespace std;
int nx, ny; //X和Y 集合中顶点的个数
int g[305][305]; //邻接矩阵，g[i][j]为1 表示Xi 和Yj 有边相连
int cx[305], cy[305];
int mk[305] ;
int path( int u )
{
for( int v=1 ; v<=ny ; v++ ) //考虑所有Yi 顶点v
{
if( g[u][v] && !mk[v] ) //v 与u 邻接，且没有访问过
{
mk[v]=1; //访问v
//如果v 没有匹配，或者v 已经匹配了，但从cy[v]出发可以找到一条增广路
//注意如果前一个条件成立，则不会递归调用
if( cy[v]==-1||path( cy[v] ) )
{
cx[u]=v; //把v 匹配给u
cy[v]=u; //把u 匹配给v
return 1; //找到可增广路
}
}
}
return 0 ; //如果不存在从u 出发的增广路
}
int MaxMatch( ) //求二部图最大匹配的匈牙利算法
{
int res=0; //所求得的最大匹配
memset(cx,0xff,sizeof(cx)); //从0 匹配开始增广,将cx 和cy 各元素初始化为-1
memset( cy, 0xff, sizeof(cy) );
for( int i=1; i<=nx; i++ )
{
if( cx[i]==-1 ) //从每个未盖点出发进行寻找增广路
{
memset( mk, 0, sizeof(mk) ) ;
res+=path(i); //每找到一条增广路，可使得匹配数加1
}
}
return res;
}
int main()
{
int i,j,T,p,n,max;
cin>>T;
while(T--)
{
memset(g,0,sizeof(g));
cin>>nx>>ny;
for(i=1;i<=nx;i++)
{
cin>>p;
for(j=1;j<=p;j++)
{
cin>>n;
&
补充：软件开发 , C++ ,
