算法練習系列—hiho1122二分圖最大匹配之匈牙利算法

算法練習系列—hiho1122二分圖最大匹配之匈牙利算法

題目地址：http://hihocoder.com/problemset/problem/1122

該題目的關鍵是2個問題：1點用bfs構造二分圖 2：針對二分圖的其中S中的結點，遍歷找增廣路(匈牙利算法求二分圖的最大匹配) 每找到一條增廣路就多找到了一條匹配。

代碼如下：

/*
這題有兩點需要注意：1點用bfs構造二分圖   
2：針對二分圖的其中S中的結點，遍歷找增廣路(匈牙利算法求二分圖的最大匹配)
每找到一條增廣路 就多找到了一條匹配
*/
#include 
#include 
#include 
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 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點)，然後一個個的尋找算法進行解決