| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
贴个c++代码#include <iostream>
using namespace std;
int G[2501][1250];//邻接表
int deg[2501];//每个节点的度
int match[2501];//与节点配对的节点
bool used[1251];//记录节点是否已被搜索过
int F[51][51];//记录与 (i, j) 相连的纵向节点
void add_edge(int u, int w);
bool dfs(int v);
int main()
{
int R, C, rp, cp = 0, ans = 0;// rp cp 分别是横向和纵向的节点数
char ch;
cin >> R >> C;
for (int i = 1; i <= R; i++)
{
for (int j = 1; j <= C; j++)
{
cin >> ch;
if (ch == '*')
{
if (!F[i][j - 1])
{
cp++;
}
F[i][j] = cp;
}
}
}
rp = cp;
for (int j = 1; j <= C; j++)
{
for (int i = 1; i <= R; i++)
{
if (F[i][j])
{
if (!F[i - 1][j])
{
rp++;
}
add_edge(F[i][j], rp);
}
}
}
for (int i = 1; i <= cp; i++)
{
for (int j = 1; j <= cp; j++)
{
used[j] = false;
}
if (dfs(i))
{
ans++;
}
}
cout << ans << '\n';
return 0;
}
void add_edge(int u, int w)
{
G[u][deg[u]++] = w;
G[w][deg[w]++] = u;
return;
}
bool dfs(int v)
{
int u, w;
used[v] = true;
for (int i = 0; i < deg[v]; i++)
{
u = G[v][i];
w = match[u];
if (!w)
{
match[v] = u;
match[u] = v;
return true;
}
else if (!used[w])
{
if (dfs(w))
{
match[v] = u;
match[u] = v;
return true;
}
}
}
return false;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator