Posted on 2008-08-01 15:19
Hero 阅读(228)
评论(0) 编辑 收藏 引用 所属分类:
代码如诗－－ACM
1 /*
2 ID: wangzha4
3 LANG: C++
4 TASK: stall4
5 */
6
7 //二部图匹配
8 /*
9 对上部点逐个寻找连接,找到则连接数+1:
10
11 对于一上部点u,若能找到一下部点v,u与v匹配,且v未被连接,则连接u与v,连接数+1
12
13 对于一上部点u,若能找到一下部点v,u与v匹配
14
15 而v已与u'连接
16
17 若u'能找到另一可连接的匹配v'.则可以通过连接u-v,u'-v'使连接数+1
18
19 红色部分是一个递归过程,一直到能找到一个未连接的下部点为止,修改连接,返回1.
20
21 或找不到这样一个点,返回0
22 */
23
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <ctype.h>
28 #define llong unsigned long long
29 #define unint unsigned int
30 #define printline printf( "\n" )
31
32 double fmax( double a, double b )
33 {
34 if( a - b > 0 ) return a ;
35 else return b ;
36 }
37
38 double fmin( double a, double b )
39 {
40 if( a - b < 0 ) return a ;
41 else return b ;
42 }
43
44 int fmax( int a, int b )
45 {
46 if( a > b ) return a ;
47 else return b ;
48 }
49
50 int fmin( int a, int b )
51 {
52 if( a < b ) return a ;
53 else return b ;
54 }
55
56 int fpow( int a, int b )
57 {
58 int reval = 1 ;
59 for( int i=1; i<=b; i++ )
60 reval *= a ;
61 return reval ;
62 }
63 const int INF = 1000000 ;
64 const int size = 210 ;
65
66 int inn ;//奶牛数量
67 int inm ;//牛栏数量
68 bool link[size][size] ;//邻接矩阵(两个点是否可以连接
69 bool visit[size] ;//标记下部图的点是否被访问过
70 int match[size] ;//记录下部图的对应匹配点－－需要更新
71
72 int DFS_findpath( int sn )
73 {
74 for( int i=1; i<=inm; i++ ) {//枚举下部图的点为对应点
75 if( false==visit[i]&&link[sn][i] ) {//if可以匹配且可以访问
76 visit[i] = true ;//标记掉这个点是为了递归的时候不重复找
77 if( -1==match[i] || DFS_findpath(match[i]) ) {
78 //如果这个点尚且没有匹配的上部图的点或者这个点已经匹配上部图(u)
79 //但是可以在下部图中找到没有匹配的点(v),使(u)与(v)匹配(sn)与(i)匹配
80 //更新(i)的match[i] 返回 1 ; 否则返回 0 ；
81 match[i] = sn ; return 1 ;
82 }
83 }
84 }
85
86 return 0 ;
87 }
88
89 int Binmatch( )
90 {
91 int matchnum = 0 ;
92 memset( match, -1, sizeof(match) ) ;//下部图的点均未匹配
93
94 for( int i=1; i<=inn; i++ ) {//枚举上部图的点
95
96 memset( visit, false, sizeof(visit) ) ;
97 matchnum += DFS_findpath( i ) ;
98 }
99
100 return matchnum ;
101 }
102
103 int main()
104 {
105 freopen( "stall4.in", "r", stdin ) ;
106 freopen( "stall4.out","w",stdout ) ;
107
108 scanf( "%d %d", &inn, &inm ) ;
109
110 int numlink ; int en ;
111 for( int sn=1; sn<=inn; sn++ ) {
112
113 scanf( "%d", &numlink ) ;
114 for( int j=1; j<=numlink; j++ ) {
115 scanf( "%d", &en ) ; link[sn][en] = true ;
116 }
117 }//data input
118
119 int matchnum = Binmatch() ;
120
121 printf( "%d\n",matchnum ) ;
122
123 return 0 ;
124 }