题目大意：在一个N*N的矩阵里寻找最多有多少个“##”（横着竖着都行）。
题目分析：重新构图,直接以相邻的两个油井算中间算以条边，然后进行匹配，看看两两之间最多能匹配多少对。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> #include<queue> #include<cmath> using namespace std; #define INF 0x3fffffff #define maxn 605 int n, OilNum, k;///重构图之后顶点的个数 OilNum int Head[maxn]; int maps[maxn][maxn], P[maxn]; bool vis[maxn]; struct Node { int e, next; }edge[maxn]; void AddEdge(int s,int e) { edge[k].next = Head[s]; edge[k].e = e; Head[s] = k ++; } bool Find(int u) { for(int i=Head[u]; i != -1; i = edge[i].next) { int v = edge[i].e; if(!vis[v]) { vis[v] = true; if(P[v] == -1 || Find(P[v])) { P[v] = u; return true; } } } return false; } int solve() { int ans = 0; memset(P, -1, sizeof(P)); for(int i=1; i<=OilNum; i++) { memset(vis, false, sizeof(vis)); if(Find(i)) ans ++; } return ans / 2; } int main() { int T, cas = 1; char str[maxn]; scanf("%d", &T); while(T--) { scanf("%d", &n); k = OilNum = 0; memset(Head, -1, sizeof(Head)); memset(maps, 0, sizeof(maps)); for(int i=0; i<n; i++)///读入图，并且重新标记 { scanf("%s", str); for(int j=0; j<n; j++) { if(str[j] == '.') maps[i+1][j+1] = 0; if(str[j] == '#') maps[i+1][j+1] = ++OilNum; } } for(int i=1; i<=n; i++)///重新构图 { for(int j=1; j<=n; j++) { if(maps[i][j]) { if(maps[i-1][j]) AddEdge(maps[i][j], maps[i-1][j]); if(maps[i+1][j]) AddEdge(maps[i][j], maps[i+1][j]); if(maps[i][j-1]) AddEdge(maps[i][j], maps[i][j-1]); if(maps[i][j+1]) AddEdge(maps[i][j], maps[i][j+1]); } } } printf("Case %d: %d ", cas ++,solve()); } return 0; } /* 3 1 0 1 1 0 1 0 1 0 */