匹配

 1 //KM 邻接矩阵
 2 const int INF = 0x3f3f3f3f;
 3 
 4 int n, pay[305][305];
 5 int match[305];//y方点对应的x方点
 6 int lx[305], ly[305];//标号
 7 int slack[305];//记录标号改变量
 8 bool visx[305], visy[305];
 9 
10 bool Hungary( int s ){
11     visx[s] = true;
12 
13     for( int i = 1; i <= n; i++ ){
14         if( visy[i] ) continue;
15         if( lx[s] + ly[i] == pay[s][i] ){
16             visy[i] = true;
17             if( match[i] == -1 || Hungary( match[i] ) ){
18                 match[i] = s;
19                 return true;
20             }
21         }
22         else slack[i] = min( slack[i], lx[s] + ly[i] - pay[s][i] );
23     }
24 
25     return false;
26 }
27 
28 void KM(){
29     memset( match, -1, sizeof( match ) );
30     memset( lx, 0, sizeof( lx ) );
31     memset( ly, 0, sizeof( ly ) );
32     for( int i = 1; i <= n; i++ )
33         for( int j = 1; j <= n; j++ )
34             lx[i] = max( lx[i], pay[i][j] );
35 
36     for( int i = 1; i <= n; i++ ){
37         memset( slack, INF, sizeof( slack ) );
38         while( 1 ){
39             memset( visx, false, sizeof( visx ) );
40             memset( visy, false, sizeof( visy ) );
41 
42             if( Hungary( i ) ) break;
43             else{
44                 int temp = INF;
45                 for( int i = 1; i <= n; i++ )
46                     if( !visy[i] )
47                         temp = min( temp, slack[i] );
48                 for( int i = 1; i <= n; i++ ){
49                     if( visx[i] )
50                         lx[i] -= temp;
51                     if( visy[i] )
52                         ly[i] += temp;
53                     else
54                         slack[i] -= temp;
55                 }
56             }
57         }
58     }
59 }

 1 //前向星 + 匈牙利bfs
 2 const int MAXN = 105;
 3 const int MAXM = 10005;
 4 ////////////////////////////////////
 5 struct Match{
 6     int to, next;
 7 }ptos[MAXM], stop[MAXM];
 8 int pcnt, ph[MAXN], scnt, sh[MAXN];
 9 
10 int pmatch[MAXN], smatch[MAXN];//p和s匹配的对象
11 int flag[MAXN], pre[MAXN];
12 
13 inline void init(){
14     memset( pmatch, -1, sizeof( pmatch ) );
15     memset( smatch, -1, sizeof( smatch ) );
16     memset( ph, -1, sizeof( ph ) );
17     memset( sh, -1, sizeof( sh ) );
18     memset( flag, -1, sizeof( flag ) );
19     pcnt = scnt = 0;
20 }
21 
22 void match_add( int from, int to ){
23     ptos[pcnt].to = to;
24     ptos[pcnt].next = ph[from];
25     ph[from] = pcnt++;
26 
27     swap( from, to );
28 
29     stop[scnt].to = to;
30     stop[scnt].next = sh[from];
31     sh[from] = scnt++;
32 }
33 
34 int maxmatch(){
35     int ans = 0;
36 
37     for( int i = 1; i <= n; i++ ){
38         if( pmatch[i] == -1 ){
39             queue<int> Q;
40             Q.push( i );
41             pre[i] = -1;
42             bool ok = false;
43 
44             while( !Q.empty() && !ok ){
45                 int pos = Q.front(); Q.pop();
46 
47                 for( int k = ph[pos]; k != -1 && !ok; k = ptos[k].next ){
48                     int v = ptos[k].to;
49                     if( flag[v] != i ){
50                         flag[v] = i;
51                         Q.push( smatch[v] );
52                         if( smatch[v] == -1 ){
53                             ok = true;
54                             int tempp = pos, temps = v;
55                             while( tempp != -1 ){
56                                 int x = pmatch[tempp];
57                                 pmatch[tempp] = temps;
58                                 smatch[temps] = tempp;
59                                 tempp = pre[tempp];
60                                 temps = x;
61                             }
62                         }
63                         else pre[smatch[v]] = pos;
64                     }
65                 }
66             }
67             if( pmatch[i] != -1) ans++;
68         }
69     }
70 
71     return ans;
72 }