Posted on 2008-08-01 15:19
Hero 閱讀(252)
評論(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 }