付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

这道题 就是利用匈牙利算法 然后将问题转化为 最大匹配问题 view plaincopy to clipboardprint?
#include  <iostream>   
 

const   int   MaxN = 500 + 1;   
bool   map[MaxN][MaxN] , ck[MaxN];   
int     n , match[MaxN] , max_match , k;    
bool  search(int x)   
{   
      
int i , t;   
      
for (i = 1 ; i <= n ; i ++)   
      
if (map[i][x]&&!ck[i])   
      
{   
          ck[i] 
= true;   
          t 
= match[i];   
          match[i] 
= x;   
          
if (t ==0 || search(t)) return true;   
          match[i] 
= t;                              
      }
   
      
return false;         
}
   
void  hungary()   
{   
      
int  i ;   
      memset(match , 
0 , sizeof(match));   
      max_match 
= 0;   
      
for ( i = 1 ; i <= n ; i ++)   
      
{   
         memset(ck , 
false , sizeof(ck));   
         
if (search(i)) max_match++;   
      }
         
}
   
int   main()   
{   
        
      
int i  , x , y;   
      scanf(
"%d%d",&n,&k);   
      
for ( i = 1 ; i <= k ; i++)   
      
{   
              scanf(
"%d%d",&x,&y);   
              map[x][y] 
= true;   
      }
   
      hungary();   
      printf(
"%d\n",max_match);    
         
      
return 0;         
}
  
#include  
<iostream>

const   int   MaxN = 500 + 1;
bool   map[MaxN][MaxN] , ck[MaxN];
int     n , match[MaxN] , max_match , k; 
bool  search(int x)
{
      
int i , t;
      
for (i = 1 ; i <= n ; i ++)
      
if (map[i][x]&&!ck[i])
      
{
          ck[i] 
= true;
          t 
= match[i];
          match[i] 
= x;
          
if (t ==0 || search(t)) return true;
          match[i] 
= t;                           
      }

      
return false;      
}

void  hungary()
{
      
int  i ;
      memset(match , 
0 , sizeof(match));
      max_match 
= 0;
      
for ( i = 1 ; i <= n ; i ++)
      
{
         memset(ck , 
false , sizeof(ck));
         
if (search(i)) max_match++;
      }
      
}

int   main()
{
     
      
int i  , x , y;
   scanf(
"%d%d",&n,&k);
      
for ( i = 1 ; i <= k ; i++)
      
{
              scanf(
"%d%d",&x,&y);
              map[x][y] 
= true;
      }

      hungary();
      printf(
"%d\n",max_match); 
      
      
return 0;      
}

 

 

 完全是 模板的套用 呵呵


 

posted on 2009-08-04 17:05 付翔 阅读(919) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2009年8月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜