匈牙利算法

先附上一片生动的匈牙利算法讲解~

http://blog.csdn.net/dark_scope/article/details/8880547

再配上一道题~

http://soj.sysu.edu.cn/show_problem.php?pid=1000&cid=1854

最后配上代码~

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 int graph[105][105];
 6 bool vis[105];
 7 int pre[105];
 8 
 9 int dfs(int cur, int m)
10 {
11     for(int i=1; i<=m; i++)
12     {
13         if(!vis[i] && graph[cur][i])
14         {
15             vis[i]=1;
16             if(pre[i] == -1 || dfs(pre[i], m))
17             {
18                 pre[i] = cur;
19                 return 1;
20             }
21         }
22     }    
23     return 0;
24 }
25 
26 int main()
27 {
28     int n, m;
29     while(cin >> n >> m)
30     {
31         int sum=0;
32         memset(vis,0,sizeof(vis));
33         memset(pre,-1,sizeof(pre));
34         
35         for(int i=1; i<=n; i++)
36             for(int j=1; j<=m; j++)
37                 cin >> graph[i][j];
38         for(int i=1; i<=n; i++)
39         {
40             memset(vis, 0, sizeof(vis));
41             sum += dfs(i, m);
42         }
43         cout << sum << endl;
44     }
45     
46     return 0;
47 }