二分图最大匹配：匈牙利算法

 1 #include<bits/stdc++.h>
 2 #define ll long long 
 3 #define scan(i) scanf("%d",&i)
 4 #define scand(i) scanf("%lf",&i)
 5 #define scanl(i) scanf("%lld",&i)
 6 #define f(i,a,b) for(int i=a;i<=b;i++) 
 7 #define pb(i) push_back(i)
 8 #define ppb pop_back()
 9 #define pf printf
10 using namespace std;
11 int t,n,k; 
12 int m[102][102]; 
13 set<int> color;
14 set<int> no;
15 int curcolor;
16 bool edge[102][102];
17 bool vis[102];//女孩有主否 
18 int col[102];
19 bool find(int x){//x能否找到伴侣 
20     f(i,1,n){
21         if(edge[x][i]==true&&vis[i]==false){
22             vis[i]=true;
23             if(col[i]==0||find(col[i])==true){
24                 col[i]=x;
25                 return true;
26             }
27         }
28     }
29     return false;
30 }
31 int maxmatch(){//返回二分图匹配最大数 
32     memset(col,0,sizeof(col));
33     int ans=0;
34     f(i,1,n){
35         memset(vis,0,sizeof(vis));
36         if(find(i)) ans++;
37     }
38     return ans;
39 }
40 int main(){
41     while(scanf("%d%d",&n,&k)!=EOF){
42         if(n==0&&k==0) return 0;
43         no.clear();
44         f(i,1,n){
45             f(j,1,n) scan(m[i][j]),color.insert(m[i][j]);
46         }
47         if(k>=n){
48             pf("-1
");
49             continue;
50         }
51         auto point=color.begin();
52         while(point!=color.end()){
53             memset(edge,0,sizeof(edge));
54             curcolor=*point;
55             point++;
56             f(i,1,n){
57                 f(j,1,n){
58                     if(m[i][j]==curcolor){
59                         edge[i][j]=true;
60                     }
61                 }
62             }
63             if(maxmatch()>k) no.insert(curcolor);
64         }
65         
66         if(no.empty()){
67             pf("-1
");
68             continue;
69         }
70         else{
71             auto it=no.begin();
72             pf("%d",*it);
73             it++;
74             for(;it!=no.end();it++){
75                 pf(" %d",*it);
76             }
77             putchar('
');
78         }
79         //pf("Case #%d: %lld
",kk,ans);
80     }
81     return 0;
82 }
二分图匹配问题，我以HDU balloon 1498为例