Posted on 2008-08-01 18:32
Hero 阅读(202)
评论(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, -1, sizeof(upmatch) ) ;
30 memset( dnmatch, -1, sizeof(dnmatch) ) ;
31
32 for( int i=1; i<=inn; i++ ) {
33 for( int j=1; j<=inm; j++ ) prev[j] = -2 ;
34 head = tail = 0 ;
35
36 for( int 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 for( int 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, false, sizeof(link) ) ; inm = inn ;
70
71 for( int k=1; k<=inn; k++ ) {
72 scanf( "%d: (%d) ", &sn, &numlink ) ; sn++ ;
73 for( int 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