HDU 1045 Fire Net（图匹配）
题目大意：
这个是以前做过的一道DFS题目，当时是完全暴力写的。
给你一个N代表是N*N的矩阵，矩阵内 ‘X’代表墙， ‘.’代表通道。
问这个矩阵内最多可以放几个碉堡， 碉堡不能在同一行或者同一列，除非他们中间有墙。
二分图做法思想：我们用行去匹配列，判断最大匹配数。
我们需要重新构图， 假如一行中 （ ..X..X.. ） 那么在这一行中我们其实是可以分割到三个不同的行（因为中间隔有X）。然后对这个三个行进行编号。同理列也是一样的。当我们完全构好图后就可以做完全匹配了，其他的跟HDU 1083 Courses（最大匹配模版题） 差不多。
吐槽一下杭电，代码写好了提交用C++WA G++过 妈蛋
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define maxn 50 bool G[maxn][maxn];///重新构图存储 bool vis[maxn];///标记点是否被遍历过 char maps[maxn][maxn];///地图存储 int P[maxn];///第 i 行匹配的第 P[i]列 int n, m, N;///重构图后是m行 n列 struct Node { int x, y; }NodeInfo[maxn][maxn];///保存每个点重构图后所在的行和列 bool Find(int u) { for(int i=0; i<n; i++) { if(G[u][i] && !vis[i]) { vis[i] = true; if( P[i] == -1 || Find(P[i])) { P[i] = u; return true; } } } return false; } void MakeMaps() { m = 0, n = 0;///行标记 和 列标记 for(int i=0; i<N; i++)///第 i 行 { for(int j=0; j<N; j++) { if(maps[i][j] == '.') NodeInfo[i][j].x = m; if(maps[i][j+1] == 'X' || maps[i][j+1] == 0) m ++; } } for(int i=0; i<N; i++)///第 i 列 { for(int j=0; j<N; j++) { if(maps[j][i] == '.') NodeInfo[j][i].y = n; if(maps[j+1][i] == 'X' || maps[j+1][i] == 0) n ++; } } for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { int x = NodeInfo[i][j].x; int y = NodeInfo[i][j].y; if(maps[i][j] == '.') G[x][y] = true; } } } int main() { while(scanf("%d", &N), N) { memset(G, 0, sizeof(G)); memset(P, -1, sizeof(P)); memset(maps, 0, sizeof(maps)); for(int i=0; i<N; i++) scanf("%s", maps[i]); MakeMaps(); int ans = 0; for(int i=0; i<m; i++) { memset(vis, false, sizeof(vis)); if( Find(i) ) ans ++; } printf("%d ", ans); } return 0; }