Fire Net HDU - 1045（二分匹配）

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <vector>#include <cmath>#include <algorithm>#define mem(a, b) memset(a, b, sizeof(a))using namespace std;const int maxn = 10010, INF = 0x7fffffff;int dx[maxn], dy[maxn], cx[maxn], cy[maxn], used[maxn];int row[5][5], col[5][5];int nx, ny, dis;vector<int> G[40005];char str[5][5];int n;int bfs(){ ???queue<int> Q; ???dis = INF; ???mem(dx, -1); ???mem(dy, -1); ???for(int i=1; i<=nx; i++) ???{ ???????if(cx[i] == -1) ???????{ ???????????Q.push(i); ???????????dx[i] = 0; ???????} ???} ???while(!Q.empty()) ???{ ???????int u = Q.front(); Q.pop(); ???????if(dx[u] > dis) break; ???????for(int v=0; v<G[u].size(); v++) ???????{ ???????????int i = G[u][v]; ???????????if(dy[i] == -1) ???????????{ ???????????????dy[i] = dx[u] + 1; ???????????????if(cy[i] == -1) dis = dy[i]; ???????????????else ???????????????{ ???????????????????dx[cy[i]] = dy[i] + 1; ???????????????????Q.push(cy[i]); ???????????????} ???????????} ???????} ???} ???return dis != INF;}int dfs(int u){ ???for(int v=0; v<G[u].size(); v++) ???{ ???????int i = G[u][v]; ???????if(!used[i] && dy[i] == dx[u] + 1) ???????{ ???????????used[i] = 1; ???????????if(cy[i] != -1 && dis == dy[i]) continue; ???????????if(cy[i] == -1 || dfs(cy[i])) ???????????{ ???????????????cy[i] = u; ???????????????cx[u] = i; ???????????????return 1; ???????????} ???????} ???} ???return 0;}int hk(){ ???int res = 0; ???mem(cx, -1); ???mem(cy, -1); ???while(bfs()) ???{ ???????mem(used, 0); ???????for(int i=1; i<=nx; i++) ???????{ ???????????if(cx[i] == -1 && dfs(i)) res++; ???????} ???} ???return res;}int main(){ ???while(cin>> n && n) ???{ ???????for(int i=0; i<100; i++) G[i].clear(); ???????mem(row, -1); ???????mem(col, -1); ???????nx = ny = 1; ???????for(int i=0; i<n; i++) ???????{ ???????????cin>> str[i]; ???????} ???????for(int i=0; i<n; i++) ???????{ ???????????for(int j=0; j<n; j++) ???????????{ ???????????????if(str[i][j] == ‘.‘ && row[i][j] == -1) ???????????????{ ???????????????????for(int k=j; str[i][k]==‘.‘ && k<n; k++) ???????????????????????row[i][k] = nx; ???????????????????nx++; ???????????????} ???????????????if(str[j][i] == ‘.‘ && col[j][i] == -1) ???????????????{ ???????????????????for(int k=j; str[k][i]==‘.‘ && k<n; k++) ???????????????????????col[k][i] = ny; ???????????????????ny++; ???????????????} ???????????} ???????} ???????nx -= 1, ny -= 1; ???????for(int i=0; i<n; i++) ???????????for(int j=0; j<n; j++) ???????????????if(str[i][j] == ‘.‘) ???????????????????G[row[i][j]].push_back(nx + col[i][j]), G[nx + col[i][j]].push_back(row[i][j]); ???????cout<< hk() <<endl; ???} ???return 0;}

#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#define mem(a,b) memset(a,b,sizeof(a))using namespace std;const int maxn = 6, INF = 0xfffffff;typedef long long LL;char str[maxn][maxn];int vis[maxn][maxn];int n, minn;int check(int x,int y){ ???for(int i=x-1; i>=0; --i) ???{ ???????if(vis[i][y]) ???????????return 0; ???????if(str[i][y] == ‘X‘) ???????????break; ???} ???for(int i=y-1; i>=0; --i) ???{ ???????if(vis[x][i]) ???????????return 0; ???????if(str[x][i] == ‘X‘) ???????????break; ???} ???return 1;}void dfs(int inx, int k){ ???if(inx == n*n) ???{ ???????minn = max(k, minn); ???????return; ???} ???int x = inx / n; ???int y = inx % n; ???if(str[x][y] == ‘.‘ && check(x,y)) ???{ ???????vis[x][y] = 1; ???????dfs(inx+1, k+1); ???????vis[x][y] = 0; ???} ???dfs(inx+1, k);}int main(){ ???while(cin>>n && n) ???{ ???????minn = -INF; ???????mem(vis,0); ???????mem(str,0); ???????for(int i=0;i<n;i++) ???????????cin>>str[i]; ???????dfs(0,0); ???????cout<<minn<<endl; ???} ???return 0;}