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;
                g[i][n]=1;
            }
        }
        max=MaxMatch();
        if(max>=nx)
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 520;
}