板子（匈牙利算法，邻接矩阵）
const int MAXN=2e3+5; int uN, vN; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u) { for(int v=0; v<vN; v++) if(g[u][v] && !used[v]) { used[v]=true; if(linker[v]==-1 || dfs(linker[v])) { linker[v]=u; return true; } } return false; } int hungary() { int res=0; memset(linker, -1, sizeof(linker)); for(int u=0; u<uN; u++) { memset(used, 0, sizeof(used)); if(dfs(u)) res++; } return res; }
HDU 1045
题意：给出一张图，给出空地‘.‘和隔板‘x’, 求放置最多满足条件的blockhouse，条件：垂直和水平方向上没有如果隔板隔开的话，只能放置一个house，有隔板话，隔板的之后（相对位置）的不用考虑。
题解：分别对每一行和每一列进行缩点（重新标号），两个相交的话就连边（其实就是把2个条件链接（行，列）到了一起）
#include <bits/stdc++.h> using namespace std; #define _for(i,a,b) for(int i=(a); i< (b); i++) #define _rep(i,a,b) for(int i=(a); i<=(b); i++) const int MAXN=2e2+5; int uN, vN; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u) { for(int v=0; v<vN; v++) if(g[u][v] && !used[v]) { used[v]=true; if(linker[v]==-1 || dfs(linker[v])) { linker[v]=u; return true; } } return false; } int hungary() { int res=0; memset(linker, -1, sizeof(linker)); for(int u=0; u<uN; u++) { memset(used, 0, sizeof(used)); if(dfs(u)) res++; } return res; } char Map[MAXN][MAXN]; int Mrow[MAXN][MAXN], Mcol[MAXN][MAXN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("in.txt", "r", stdin); int n; while(cin>>n, n) { _for(i, 0, n) _for(j, 0, n) cin>>Map[i][j]; uN=vN=0; int cu=0, cv=0; memset(Mrow, -1, sizeof(Mrow)); memset(Mcol, -1, sizeof(Mcol)); _for(i, 0, n) _for(j, 0, n) { if(Mrow[i][j]==-1 && Map[i][j]==‘.‘) { for(int k=j; k<n&&Map[i][k]==‘.‘; k++) Mrow[i][k]=cu; uN=max(uN, ++cu); } if(Mcol[i][j]==-1 && Map[i][j]==‘.‘) { for(int k=i; k<n&&Map[k][j]==‘.‘; k++) Mcol[k][j]=cv; vN=max(vN, ++cv); } } memset(g, 0, sizeof(g)); _for(i, 0, n) _for(j, 0, n) if(Map[i][j]==‘.‘) g[Mrow[i][j]][Mcol[i][j]]=1; cout<<hungary()<<endl; } return 0; }
原文：https://www.cnblogs.com/Yokel062/p/11330059.html
