算法练习系列—hiho1122二分图最大匹配之匈牙利算法

桃扇骨 2022-08-07 05:46 192阅读 0赞

题目地址：[http://hihocoder.com/problemset/problem/1122][http_hihocoder.com_problemset_problem_1122]

该题目的关键是2个问题：1点用bfs构造二分图 2：针对二分图的其中S中的结点，遍历找增广路(匈牙利算法求二分图的最大匹配) 每找到一条增广路就多找到了一条匹配。

代码如下：

/*
    这题有两点需要注意：1点用bfs构造二分图   
    2：针对二分图的其中S中的结点，遍历找增广路(匈牙利算法求二分图的最大匹配)
    每找到一条增广路 就多找到了一条匹配
    */
    #include <iostream>
    #include <string.h>
    #include <queue>
    using namespace std;
    
    #define MAXSIZE 10010
    
    struct GNode{
    	int vertex;
    	GNode *adj;
    };
    
    class Graph{
    public:
    	Graph(int v, int e){   // 图构造函数初始化
    		vertexNum = v;
    		arcNum = e;
    		memset(result, 0, sizeof(result));
    		for(int i = 1; i <= vertexNum; i++){
    			color[i] = 2;
    			edges[i] = NULL;  //  局部变量必须初始化 否则就不能与NULL比较
    		}
    	}
    	void initEdges(int u, int v);   
    	
    	void showGraph();
    	bool findPath(int u);       // 遍历增广路
    
    	int visited[MAXSIZE];    // 标识是否访问过了
    	int color[MAXSIZE];   //  0 1 表示相对颜色 2表示为访问  用来构造二分图
    	~Graph(){
    		for(int i = 1; i <= vertexNum; i++)
    			destroy(edges[i]);
    	}
    	bool bfs_travel();       // 广度遍历 构造二分图
    private:
    	int vertexNum;
    	int arcNum;
    	GNode *edges[MAXSIZE];
    
    	int result[MAXSIZE];   //保存V2在V1中匹配的顶点
    	void destroy(GNode *pNode);          // 销毁图   
    	void initUndirectedEdges(int u, int v);
    	bool bfs(int v);
    };
    
    void Graph::initEdges(int u, int v){
    	initUndirectedEdges(u, v);
    	initUndirectedEdges(v, u);
    }
    void Graph::initUndirectedEdges(int u, int v){
    	GNode *adjNode = new GNode();
    	adjNode->vertex = v;
    	adjNode->adj = NULL;
    	if(edges[u] == NULL)edges[u] = adjNode;
    	else{
    		GNode *pNode = edges[u];
    		while(pNode->adj != NULL) pNode = pNode->adj;
    		pNode->adj = adjNode;
    	}
    }
    bool Graph::bfs(int v){
    	queue<int> q;
    	q.push(v);
    	color[v] = 0;
    	while(!q.empty()){
    		int u = q.front();
    		q.pop();
    		GNode *pNode = edges[u];
    		while(pNode != NULL){
    			if(color[pNode->vertex] == color[u])return false;
    			if(color[pNode->vertex] == 2){
    				q.push(pNode->vertex);
    				color[pNode->vertex] = !color[u];
    			} 
    			pNode = pNode->adj;
    			
    		}
    	}
    	return true;
    	
    }
    bool Graph::bfs_travel(){
    	for(int i = 1; i <= vertexNum; i++){
    		if(color[i] == 2)
    			if(!bfs(i))return false;
    	}
    	return true;
    }
    
    void Graph::destroy(GNode *pNode){
    	if(pNode != NULL){
    		destroy(pNode->adj);
    		delete pNode;
    	}
    }
    
    // 寻找一条增广路 
    bool Graph::findPath(int u){
    	GNode *pNode = edges[u];
    	while(pNode != NULL){
    		int v = pNode->vertex;
    		if(!visited[v]){
    			visited[v] = 1; // ==0 表示未匹配  后面表示继续找result[v]对应的S中的顶点
    			if(result[v] == 0 || findPath(result[v])){    
    				result[v] = u;
    				return true;
    			}
    		}
    		pNode = pNode->adj;
    	}
    	return false;
    }
    void Graph::showGraph(){
    	for(int i = 1; i <= vertexNum; i++){  
            cout << i << "->";  
    		GNode *p = edges[i];  
            while( p != NULL) {  
    			cout << "(" << p->vertex << ")" ;  
                p = p->adj;  
            }  
            cout << endl;  
        } 
    }
    
    int main(){
    	int N, M;
    	cin >> N >> M;    // 输入顶点和边
    	Graph g(N,M);
    	for(int i = 0; i < M; i++){
    		int u, v;
    		cin >> u >> v;
    		g.initEdges(u, v);   // 构造图 采用邻接表存储
    	}
    	//g.showGraph();
    	int ans = 0;
    	if(g.bfs_travel()){   // 是否能构成二分图及标识二分图 color[i]=0或者1
    		for(int i = 1; i <= N; i++){
    			if(!g.color[i]){
    				memset(g.visited, 0, sizeof(g.visited));
    				if(g.findPath(i))ans++;
    			}
    		}
    	}
    	cout << ans << endl;
    	return 0;
    }
    
    /*
    5 4
    3 2
    1 3
    5 4
    1 5
    */

**题后感：**

实现一个算法首要的就是(1)了解算法实现的过程(通过例子) (2)初步确定算法所需要的数据结构

(3)编码实现

针对一个大的问题或项目，头脑中立刻要想到需要解决的难点问题(比如本题就有2点)，然后一个个的寻找算法进行解决

[http_hihocoder.com_problemset_problem_1122]: http://hihocoder.com/problemset/problem/1122