POJ 1274

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include <string.h>
 4 #include <vector>
 5 #define MAXN 251
 6 #define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
 7 #define _clr(x) memset(x,0xff,sizeof(int)*MAXN) 
 8 
 9 using namespace std;
10 
11 int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2);
12 int _m[MAXN][MAXN];
13 int match1[MAXN];
14 int match2[MAXN];
15 int main()
16 {
17     //freopen("acm.acm","r",stdin);
18     int M;
19     int N;
20     int n;
21     int i;
22     int j;
23 //    bool M_N;
24     int s;
25     while(cin>>M>>N)
26     {
27 //    if(M <= N)
28 //        M_N = true;
29     for(i = 0; i < MAXN; ++i)
30     {
31         memset(_m[i],0,sizeof(int)*MAXN);
32     }
33     for(i = 0; i < M; ++ i)
34     {
35         cin>>s;
36         for(j = 0; j < s; ++ j)
37         {
38             cin>>n;
39 //            if(M_N)
40 //            {
41                 _m[i][n-1] = 1;
42 //            }
43 //            else
44 //            {
45 //                _m[n-1][i] = 1;
46 //            }
47         }
48     }
49 //    if(M_N)
50         cout<<hungary(M,N,_m,match1,match2)<<endl;
51 //    else
52 //        cout<<hungary(N,M,_m,match1,match2)<<endl;
53     }
54 }
55 
56 
57 int hungary(int m,int n,int mat[][MAXN],int * match1,int* match2){
58     int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;
59     for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
60         for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
61             for (k=s[p],j=0;j<n&&match1[i]<0;j++)
62                 if (mat[k][j]&&t[j]<0){
63                     s[++q]=match2[j],t[j]=k;
64                     if (s[q]<0)
65                         for (p=j;p>=0;j=p)
66                             match2[j]=k=t[j],p=match1[k],match1[k]=j;
67                 }
68     return ret;
69 }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com