本文主要是介绍二分最大匹配总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 2444 黑白染色 ，二分图判定
const int maxn = 208 ;
vector<int> g[maxn] ;
int n ;
bool vis[maxn] ;
int match[maxn] ;;
int color[maxn] ;
int setcolor(int u , int c){color[u] = c ;for(vector<int>::iterator it = g[u].begin() ; it != g[u].end() ; it++){if(color[*it] == -1) {if(! setcolor(*it , c^1)) return 0 ;}else if(color[*it] == color[u]) return 0 ;}return 1 ;
}int judge(){for(int i = 1 ; i <= n ; i++){if(color[i] == -1){if(! setcolor(i , 0)) return 0 ;}}return 1 ;
}int dfs(int u){for(vector<int>::iterator it = g[u].begin() ; it != g[u].end() ; it++){if(vis[*it]) continue ;vis[*it] = 1 ;if(match[*it] == -1 || dfs(match[*it])){match[*it] = u ;return 1 ;}}return 0 ;
}int maxmatch(){int ans = 0 , u ;memset(match , -1 , sizeof(match)) ;for(u = 1 ; u <= n ; u++){memset(vis , 0 , sizeof(vis)) ;if(dfs(u)) ans++ ;}return ans ;
}int main(){int m , i , j , u , v ;while(cin>>n>>m){for(i = 1 ; i <= n ; i++) g[i].clear() ;for(i = 1 ; i <= m ; i++){scanf("%d%d" ,&u,&v) ;g[u].push_back(v) ;g[v].push_back(u) ;}for(i = 1 ; i <= n ; i++) color[i] = -1 ;if(judge()) printf("%d\n" , maxmatch() >> 1) ;else puts("No") ;}return 0 ;
}
HDU 4185 在一个N*N的矩阵里寻找最多有多少个“##”（横着竖着都行）
很典型的二分匹配问题，将矩阵中的点分成俩种，下标i+j为奇数和偶数俩种，即把矩阵当成一个黑白棋盘，那么，一个木板只能覆盖一个黑色和一个白色格子，将黑色格子（并且是‘#’的格子）跟相邻的白色（并且是‘#’）的格子连一条边，则变成了一个求最大匹配的问题了
const int maxn = 601*601*2 ;
int n , m ;
vector<int> g[maxn] ;
int match[maxn] ;
bool vis[maxn] ;int dfs(int u){for(vector<int>::iterator it = g[u].begin() ; it != g[u].end() ; it++){if(vis[*it]) continue ;vis[*it] = 1 ;if(match[*it] == -1 || dfs(match[*it])){match[*it] = u ;return 1 ;}}return 0 ;
}int maxmatch(){int ans = 0 , u ;memset(match , -1 , (m+1)*sizeof(int)) ;for(u = 1 ; u <= n ; u++){memset(vis , 0 , (m+1)*sizeof(bool)) ;if(dfs(u)) ans++ ;}return ans ;
}char str[608][608] ;
int N ;
map<int ,int> A , B ;
int d[4][2] = {{-1,0},{1,0},{0,-1},{0,1}} ;inline int can(int x , int y){return 1 <= x && x<= N && 1 <= y && y <= N && str[x][y] == '#' ;
}int code(int x , int y){return (x-1)*N + y ;
}int main(){int t , i , j , u , v , indxA , indxB ,k, x , y , T = 1 ;cin>>t ;while(t--){scanf("%d" ,&N) ;for(i = 1 ; i <= N ; i++) scanf("%s" ,str[i]+1) ;A.clear() , B.clear() ;indxA = indxB = 0 ;for(i = 1 ; i <= N ; i++){for(j = 1 ; j <= N ; j++){if(((i+j)&1) && str[i][j] == '#'){for(k = 0 ; k < 4 ; k++){x = i + d[k][0] ; y = j + d[k][1] ;if(can(x,y)){u = code(i , j) ;v = code(x , y) ;if(A.find(u) == A.end()) A[u] = ++indxA ;if(B.find(v) == B.end()) B[v] = ++indxB ;g[A[u]].push_back(B[v]) ;}}}}}n = indxA ;m = indxB ;printf("Case %d: %d\n" , T++ , maxmatch() ) ;for(i = 1 ; i <= n ; i++) g[i].clear() ;}return 0 ;
}
这篇关于二分最大匹配总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
