[ 登录注册 ]

语言

UESTC 919 SOUND OF DESTINY --二分图最大匹配+匈牙利算法

2017-07-14 10:27:02 admin 返回上一页

标签:des   style   class   blog   code   http   

二分图最大匹配的匈牙利算法模板题。

由题目易知,需求二分图的最大匹配数,采取匈牙利算法,并采用邻接表来存储边,用邻接矩阵会超时,因为邻接表复杂度O(nm),而邻接矩阵最坏情况下复杂度可达O(n^3)。

代码:

bubuko.com布布扣
#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>using namespace std;#define N 1007int vis[N];int match[N];int nm;vector<int> G[N];int Search_Path(int s){for(int i=0;i<G[s].size();i++){int v = G[s][i];if(!vis[v]){vis[v] = 1;if(match[v] == -1 || Search_Path(match[v])){match[v] = s;return 1;}}}return 0;}int main(){int cntijk;int ab;scanf("%d%d"&n&m);for(i=0;i<=n;i++)G[i].clear();scanf("%d"&k);memset(match-1sizeof(match));for(i=0;i<k;i++){scanf("%d%d"&a&b);a--b--;G[a].push_back(b);}cnt = 0;for(i=0;i<n;i++){memset(vis0sizeof(vis));if(Search_Path(i))cnt++;}printf("%d
"cnt);return 0;}
View Code

 

UESTC 919 SOUND OF DESTINY --二分图最大匹配+匈牙利算法布布扣bubuko.com

UESTC 919 SOUND OF DESTINY --二分图最大匹配+匈牙利算法

标签:des   style   class   blog   code   http   


文章来源:http://www.bozhiyue.com/yuyan/2017/0714/1484256.html
返回上一页    返回分类 上一篇:   下一篇:
相关