我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

P1719

Posted on 2008-09-10 21:14 Hero 阅读(111) 评论(0)  编辑 收藏 引用 所属分类: 代码如诗--ACM
  1 // 1719 Accepted 5908K 204MS C++ 2057B PKU
  2 
  3 //二部图匹配
  4 //X : col 1 2 3 4 5 6
  5 //Y : row 1 2 3 4
  6 //每个col到row有两条有向边
  7 
  8 #include <stdio.h>
  9 #include <string.h>
 10 #include <stdlib.h>
 11 
 12 const int size = 1200 ;
 13 int edge[size][size] ;
 14 
 15 int A[size] ;
 16 int B[size] ;
 17 
 18 int innum ;
 19 int row, col ;
 20 
 21 void input()
 22 {
 23     memset( edge, 0sizeof(edge) ) ;
 24 
 25     scanf( "%d %d"&row, &col ) ;
 26     int ina, inb ;
 27     forint c=1; c<=col; c++ )
 28     {
 29         scanf( "%d %d"&ina, &inb ) ;
 30         edge[c][ina] = 1 ; edge[c][inb] = 1 ;
 31         A[c] = ina ; B[c] = inb ;
 32     }
 33 }
 34 
 35 int Binmatch( int inn, int inm, int link[][size] )
 36 {//传入边的矩阵edge[][]-->link[][]
 37     int matchnum = 0 ; int dn_node ;
 38     int queue[size*10] ; int head=0, tail = 0 ;//定义队列
 39     int upmatch[size], dnmatch[size] ; int prev[size] ;
 40     memset( upmatch, -1sizeof(upmatch) ) ;
 41     memset( dnmatch, -1sizeof(dnmatch) ) ;
 42 
 43     forint i=1; i<=inn; i++ ) {
 44         forint j=1; j<=inm; j++ )    prev[j] = -2 ;
 45         head = tail = 0 ;
 46 
 47         forint j=1; j<=inm; j++ )    if( link[i][j] )
 48         { prev[j] = -1 ; queue[tail++= j ; }
 49 
 50         while( head < tail ) {
 51             dn_node = queue[head] ;
 52             if-1 == dnmatch[dn_node] )    break ;
 53             head++ ;
 54             forint j=1; j<=inm; j++ ) if-2==prev[j]&&link[dnmatch[dn_node]][j] )
 55             { prev[j] = dn_node ; queue[tail++= j ; }
 56         }
 57 
 58         if( head == tail )    continue ;
 59         while( prev[dn_node] > -1 ) {
 60             upmatch[dnmatch[prev[dn_node]]] = dn_node ;
 61             dnmatch[dn_node] = dnmatch[prev[dn_node]] ;
 62             dn_node = prev[dn_node] ;
 63         }
 64 
 65         dnmatch[dn_node] = i ; upmatch[i] = dn_node ;
 66         matchnum++ ;
 67     }
 68 
 69     if( matchnum != row )    printf( "NO\n" ) ;
 70     else
 71     {
 72         char * blank = "" ;
 73         forint i=1; i<=col; i++ )
 74         {
 75             if( upmatch[i] != -1 )
 76             {
 77                 printf( "%s%d", blank, upmatch[i] ) ;
 78                 blank = " " ;
 79             }
 80             else
 81             {
 82                 printf( "%s%d", blank, A[i] ) ;
 83                 blank = " " ;
 84             }
 85         }
 86         printf( "\n" ) ;
 87     }
 88 
 89     return matchnum ;
 90 }
 91 
 92 void process()
 93 {
 94     int matchnum = Binmatch( col, row, edge ) ;
 95 
 96     //printf( "matchnum == %d\n", matchnum ) ;
 97 }
 98 
 99 int main()
100 {
101     while( scanf( "%d"&innum ) != EOF )
102     {
103         forint ct=1; ct<=innum; ct++ )
104         {
105             input() ;
106 
107             process() ;
108 
109             //output() ;
110         }
111     }
112 
113     return 0 ;
114 }

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