Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 贴个c++代码

Posted by a280920481 at 2018-12-05 22:33:03 on Problem 2226
```#include <iostream>
using namespace std;

int G[2501][1250];//邻接表
int deg[2501];//每个节点的度
int match[2501];//与节点配对的节点
bool used[1251];//记录节点是否已被搜索过

int F[51][51];//记录与 (i, j) 相连的纵向节点

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++;
}
}
}
}

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;
}

{
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: