Problem :     Judge Status : Accepted

RunId : 2873274    Language : G++    Author :

Code Render Status : Rendered By HDOJ G++ Code Render Version 0.01 Beta

/***************************************************************\  *Author:Hu Wenbiao  *Created Time: Wed 25 Aug 2010 05:06:48 PM CST  *File Name: d.cpp  *Description:最小路径覆盖 \***************************************************************/ //*========================*Head File*========================*\\ #include
     
       #include
      
        #include
       
         #include
        
          /*----------------------*Global Variable*----------------------*/ int T,n,num,a,b,lx[121],ly[121]; bool G[121][121],mark[121]; //*=======================*Main Program*=======================*// using namespace std; int path(int u){
         for(int v=1;v<=n;v++){
             if(G[u][v]&&!mark[v]){
                 mark[v]=true;             if(ly[v]==-1||path(ly[v])){
                     lx[u]=v;                 ly[v]=u;                 return 1;             }         }     }     return 0; } int max_match(){
         memset(lx,-1,sizeof(lx));     memset(ly,-1,sizeof(ly));     int sum=0;     for(int i=1;i<=n;i++){
             if(lx[i]==-1){
                 memset(mark,false,sizeof(mark));             sum+=path(i);         }     }     return sum; } int main(){
         //freopen("input","r",stdin);     scanf("%d",&T);     while(T--){
             scanf("%d%d",&n,&num);         memset(G,0,sizeof(G));         while(num--){
                 scanf("%d%d",&a,&b);             G[a][b]=true;         }         printf("%d\n",n-max_match());     } }