POJ 1422

 1 #include <iostream>
 2 #define MAXN 350
 3 using namespace std;
 4 
 5 int mat[MAXN][MAXN];
 6 bool mark[MAXN];
 7 int match[MAXN];
 8 int graph_match(int n,int mat[][MAXN],int * match);
 9 int main()
10 {
11     //freopen("acm.acm","r",stdin);
12     int test;
13     int n;
14     int m;
15     int u;
16     int v;
17     int i;
18     int j;
19     cin>>test;
20     while(test --)
21     {
22         memset(mat,0,sizeof(mat));
23         memset(match,-1,sizeof(match));
24         cin>>n;
25         cin>>m;
26         for(i = 0; i < m; ++ i)
27         {
28             cin>>u;
29             cin>>v;
30             -- u;
31             -- v;
32             mat[u][v+n] = 1;
33         }
34 
35         cout<<n-graph_match(n*2,mat,match)<<endl;
36     }
37 
38 }
39 
40 
41 //一般图最大匹配,邻接阵形式,复杂度O(n^3)
42 //返回匹配顶点对数,match返回匹配,未匹配顶点match值为-1
43 //传入图的顶点数n和邻接阵mat
44 //graph_match（）为最终调用函数
45 
46 int aug(int n,int mat[][MAXN],int* match,int* v,int now){
47     int i,ret=0;
48     v[now]=1;
49     for (i=0;i<n;i++)
50         if (!v[i]&&mat[now][i]){
51             if (match[i]<0)
52                 match[now]=i,match[i]=now,ret=1;
53             else{
54                 v[i]=1;
55                 if (aug(n,mat,match,v,match[i]))
56                     match[now]=i,match[i]=now,ret=1;
57                 v[i]=0;
58             }
59             if (ret)
60                 break;
61         }
62     v[now]=0;
63     return ret;
64 }
65 int graph_match(int n,int mat[][MAXN],int * match){
66     int v[MAXN],i,j;
67     for (i=0;i<n;i++)
68     v[i]=0,match[i]=-1;
69     for (i=0,j=n;i<n&&j>=2;)
70         if (match[i]<0&&aug(n,mat,match,v,i))
71             i=0,j-=2;
72         else
73             i++;
74     for (i=j=0;i<n;i++)
75         j+=(match[i]>=0);
76     return j/2;
77 }
关注我的公众号，当然，如果你对Java, Scala, Python等技术经验，以及编程日记，感兴趣的话。
技术网站地址： vmfor.com