uestc SOUND OF DESTINY-白红宇

uestc SOUND OF DESTINY

阅读量：5252 次

发布时间：2019-06-14

本文共 4219 字，大约阅读时间需要 14 分钟。

邻接表版的DFS形式的二分匹配

增广路求最大匹配数

匈牙利算法的要点如下

从左边第 1 个顶点开始，挑选未匹配点进行搜索，寻找增广路。
1. 如果经过一个未匹配点，说明寻找成功。更新路径信息，匹配边数 +1，停止搜索。
2. 如果一直没有找到增广路，则不再从这个点开始搜索。事实上，此时搜索后会形成一棵匈牙利树。我们可以永久性地把它从图中删去，而不影响结果。

由于找到增广路之后需要沿着路径更新匹配，所以我们需要一个结构来记录路径上的点。DFS 版本通过函数调用隐式地使用一个栈，而 BFS 版本使用 prev 数组。

　　详细介绍http://www.renfei.org/blog/bipartite-matching.html

bool 寻找从k出发的对应项出的可增广路{    while (从邻接表中列举k能关联到顶点j)    {        if (j不在增广路上)        {            把j加入增广路;            if (j是未盖点 或者 从j的对应项出发有可增广路)            {                修改j的对应项为k;                则从k的对应项出有可增广路,返回true;            }        }    }    则从k的对应项出没有可增广路,返回false;}void 匈牙利hungary(){    for i->1 to n    {        if (则从i的对应项出有可增广路)            匹配数++;    }    输出 匹配数;}

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
             9 #include
             
              10 #include
              
               11 #include
               
                12 #include
                
                 13 #include
                 
                  14 #include
                  
                   15 #define INF 1e716 #define MAXN 10001017 #define maxn 100001018 #define Mod 100000719 #define N 101020 using namespace std;21 typedef long long LL;22 23 int n, m, k, a, b, ans;24 bool vis[N];25 int match[N];26 vector
                   
                     G[N];27 28 bool Search_path(int src)29 {30 for (int i = 0; i < G[src].size(); ++i) { 31 int v = G[src][i];32 if (!vis[v]) {　　　　　　　　　　　　　　33 vis[v] = true;　　　　　　　　　　　　34 if (match[v] == -1 || Search_path(match[v])) {35 match[v] = src;36 return true;37 }38 }39 }40 return false; 　　　　　　　　　　　　　　　　41 }42 43 void init()44 {45 ans = 0;46 for (int i = 0; i <= n; ++i)47 G[i].clear();48 memset(match,-1,sizeof(match));49 }50 51 int main()52 {53 while (cin >> n >> m) {54 init();55 cin >> k;56 for (int i = 0; i < k; ++i) {57 cin >> a >> b;58 a--, b--;59 G[a].push_back(b);60 }61 for (int i = 0; i < n; ++i) {62 memset(vis,0,sizeof(vis));63 if (Search_path(i))64 ans++;65 }66 cout << ans << endl;67 }68 return 0;69 }

附上模板

1 // 顶点、边的编号均从 0 开始 2 // 邻接表储存 3  4 struct Edge 5 { 6     int from; 7     int to; 8     int weight; 9 10     Edge(int f, int t, int w):from(f), to(t), weight(w) {}11 };12 13 vector
      
        G[__maxNodes]; /* G[i] 存储顶点 i 出发的边的编号 */14 vector
       
         edges;15 typedef vector
        
         ::iterator iterator_t;16 int num_nodes;17 int num_left;18 int num_right;19 int num_edges;

1 queue
      
        Q; 2 int prev[__maxNodes]; 3 int Hungarian() 4 { 5     int ans = 0; 6     memset(matching, -1, sizeof(matching)); 7     memset(check, -1, sizeof(check)); 8     for (int i=0; i
       
        = 0) { // 此点为匹配点22                             prev[matching[v]] = u;23                         } else { // 找到未匹配点，交替路变为增广路24                             flag = true;25                             int d=u, e=v;26                             while (d != -1) {27                                 int t = matching[d];28                                 matching[d] = e;29                                 matching[e] = d;30                                 d = prev[d];31                                 e = t;32                             }33                         }34                     }35                 }36                 Q.pop();37             }38             if (matching[i] != -1) ++ans;39         }40     }41     return ans;42 }

BFS

1 int matching[__maxNodes]; /* 存储求解结果 */ 2 int check[__maxNodes]; 3  4 bool dfs(int u) 5 { 6     for (iterator_t i = G[u].begin(); i != G[u].end(); ++i) { // 对 u 的每个邻接点 7         int v = edges[*i].to; 8         if (!check[v]) {     // 要求不在交替路中 9             check[v] = true; // 放入交替路10             if (matching[v] == -1 || dfs(matching[v])) {11                 // 如果是未盖点，说明交替路为增广路，则交换路径，并返回成功12                 matching[v] = u;13                 matching[u] = v;14                 return true;15             }16         }17     }18     return false; // 不存在增广路，返回失败19 }20 21 int hungarian()22 {23     int ans = 0;24     memset(matching, -1, sizeof(matching));25     for (int u=0; u < num_left; ++u) {26         if (matching[u] == -1) {27             memset(check, 0, sizeof(check));28             if (dfs(u))29                 ++ans;30         }31     }32     return ans;33 }

DFS

转载于:https://www.cnblogs.com/usedrosee/p/4294787.html

你可能感兴趣的文章