題目地址: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點),然後一個個的尋找算法進行解決