我希望你是我独家记忆

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

ZJU--1137--二部图匹配

Posted on 2008-08-01 18:32 Hero 阅读(217) 评论(0)  编辑 收藏 引用 所属分类: 代码如诗--ACM

 

 1 /*
 2 ID: wangzha4
 3 LANG: C++
 4 TASK: ZJU1137
 5 */
 6 
 7 /* Accepted 1137 C++ 00:04.35 664K */
 8 //二部图匹配
 9 
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13 #include <ctype.h>
14 #define llong unsigned long long 
15 #define unint unsigned int
16 #define printline  printf( "\n" ) 
17 
18 const int INF = 1000000 ;
19 const int size = 500 ;
20 
21 int inn, inm ; 
22 bool link[size][size] ;
23 
24 int Binmatch( int inn, int inm )
25 {
26     int matchnum = 0 ; int dn_node ;
27     int queue[size*10] ; int head=0, tail = 0 ;//定义队列
28     int upmatch[size], dnmatch[size] ; int prev[size] ;
29     memset( upmatch, -1sizeof(upmatch) ) ;
30     memset( dnmatch, -1sizeof(dnmatch) ) ;
31 
32     forint i=1; i<=inn; i++ ) {
33         forint j=1; j<=inm; j++ )    prev[j] = -2 ;
34         head = tail = 0 ;
35 
36         forint j=1; j<=inm; j++ )    if( link[i][j] )
37         { prev[j] = -1 ; queue[tail++= j ; }
38 
39         while( head < tail ) {
40             dn_node = queue[head] ;
41             if-1 == dnmatch[dn_node] )    break ;
42             head++ ;
43             forint j=1; j<=inm; j++ ) if-2==prev[j]&&link[dnmatch[dn_node]][j] )
44             { prev[j] = dn_node ; queue[tail++= j ; }
45         }
46 
47         if( head == tail )    continue ;
48         while( prev[dn_node] > -1 ) {
49             upmatch[dnmatch[prev[dn_node]]] = dn_node ;
50             dnmatch[dn_node] = dnmatch[prev[dn_node]] ;
51             dn_node = prev[dn_node] ;
52         }
53 
54         dnmatch[dn_node] = i ; upmatch[i] = dn_node ;
55         matchnum++ ;
56     }
57 
58     return matchnum ;
59 }
60 
61 int main()
62 {
63     //freopen( "frac1.in", "r", stdin ) ;
64     //freopen( "frac1.out","w",stdout ) ;
65 
66     int sn, en, numlink ;
67     while( scanf( "%d",&inn ) != EOF )
68     {
69         memset( link, falsesizeof(link) ) ; inm = inn ;
70 
71         forint k=1; k<=inn; k++ ) {
72             scanf( "%d: (%d) "&sn, &numlink ) ; sn++ ;
73             forint i=1; i<=numlink; i++ ) {
74                 scanf( "%d"&en ) ; en++ ; link[sn][en] = true ;
75             }//data input
76         }
77 
78         int matchnum = Binmatch( inn, inm ) ;
79 
80         printf( "%d\n", inn-matchnum/2 ) ;
81     }
82 
83     return 0 ;
84 }
85 

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