Posted on 2008-09-10 21:14
Hero 閱讀(121)
評論(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, 0, sizeof(edge) ) ;
24
25 scanf( "%d %d", &row, &col ) ;
26 int ina, inb ;
27 for( int 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, -1, sizeof(upmatch) ) ;
41 memset( dnmatch, -1, sizeof(dnmatch) ) ;
42
43 for( int i=1; i<=inn; i++ ) {
44 for( int j=1; j<=inm; j++ ) prev[j] = -2 ;
45 head = tail = 0 ;
46
47 for( int 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 for( int 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 for( int 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 for( int ct=1; ct<=innum; ct++ )
104 {
105 input() ;
106
107 process() ;
108
109 //output() ;
110 }
111 }
112
113 return 0 ;
114 }