题意：在大海里有一些石油 ‘#’表示石油， ‘.’表示水，有个人有一个工具可以回收这些石油，不过只能回收1*2大小的石油块，里面不能含有海水，要不就没办法使用了，求出来最多能回收多少块石油
分析：先把数据处理一下，给每一点石油都进行编号，然后查找一下四周联合是否能组成石油块，能的话就连接，因为一点有可能即在左边又在右边，所以最后的结果应该除去 2
*************************************************************************
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std; const int MAXN = 40005;///处理后点的个数
const int MAXM = 605;///原图大小
const int oo = 1e9+7; char G[MAXM][MAXM]; int N;///保存原图
int Index[MAXM][MAXM];///给石油点编号 struct Edge{int v, next;}e[MAXN*4];
int Head[MAXN], cnt;///处理后的边 int Mx[MAXN], My[MAXN];///记录与之匹配的点
int used[MAXN], dx[MAXN], dy[MAXN];///dx,dy记录BFS后的层次
int depth, NX;///宽搜的深度，和点的个数 void InIt()
{///初始化
NX = cnt = 0; memset(Head, -1, sizeof(Head));
memset(Mx, false, sizeof(Mx));
memset(My, false, sizeof(My));
}
void AddEdge(int u, int v)
{///添加边
e[cnt].v = v;
e[cnt].next = Head[u];
Head[u] = cnt++;
}
bool BFS()
{///广搜求出层次，并且判断是否有增广路存在
queue<int> Q;
depth = oo; memset(dx, false, sizeof(dx));
memset(dy, false, sizeof(dy)); for(int i=1; i<=NX; i++)
{
if( Mx[i] == false )
{
dx[i] = true;
Q.push(i);
}
} while(Q.size())
{
int u = Q.front(); Q.pop(); if( dx[u] > depth )break;///已经发现上层存在增广路 for(int j=Head[u]; j!=-1; j=e[j].next)
{
int v = e[j].v;
if( dy[v] == false )
{
dy[v] = dx[u] + 1; if(My[v] == false)
depth = dy[v];
else
{
dx[ My[v] ] = dy[v] + 1;
Q.push( My[v] );
}
}
}
} return depth != oo;
}
bool DFS(int i)
{
for(int j=Head[i]; j!=-1; j=e[j].next)
{
int v = e[j].v; if( used[v] == false && dx[i] == dy[v]-1 )
{
used[v] = true;///开始忘记置为true，错了一次
if( My[v] && dy[v] == depth )
continue;
if( !My[v] || DFS(My[v]))
{
My[v] = i;
Mx[i] = v; return true;
}
}
} return false;
}
int Karp()
{
int ans = 0; while( BFS() == true )
{
memset(used, false, sizeof(used));
for(int i=1; i<=NX; i++)
{
if( !Mx[i] && DFS(i) )
ans++;
}
} ///因为点同时在两边，所以会重复一次，结果应该出去 2
return ans / 2;
} int main()
{
int i, j, T, t=1; scanf("%d", &T); while(T--)
{
scanf("%d", &N); InIt(); for(i=0; i<N; i++)
{
scanf("%s", G[i]);
for(j=0; j<N; j++)
{
if(G[i][j] == '#')
{///购置关系图
Index[i][j] = ++NX;///给石油编号 if(j != 0 && G[i][j-1] == '#')
{///与左边的可以匹配
AddEdge(Index[i][j], Index[i][j-1]);
AddEdge(Index[i][j-1], Index[i][j]);
} if(i != 0 && G[i-1][j] == '#')
{///与上面的可以匹配
AddEdge(Index[i][j], Index[i-1][j]);
AddEdge(Index[i-1][j], Index[i][j]);;
}
}
}
} int ans = Karp(); printf("Case %d: %d\n", t++, ans);
} return 0; }