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

## 看到网上题解都是千篇一律，说说我的建图，赋AC代码

Posted by q847087628 at 2016-02-12 11:33:42 on Problem 2226
```R和C看反了，贡献两次WA，哭死
#include <stdio.h>
#include <string.h>
#define N 110
#define MAXM 3000
struct point
{
int v, w, next;
}a[MAXM];
int x[MAXM], y[MAXM];
int cnt = 0, n, m;
char ch[N][N];
void add(int u, int v, int w)
{
a[cnt].v = v;
a[cnt].w = w;
}
int dfs(int u)
{
int i;

for(i = head[u]; i != -1; i = a[i].next)
{
int v = a[i].v;
if(used[v] == 0)
{
used[v] = 1;
int w = match[v];
if(w < 0 || dfs(w))
{
match[v] = u;
return 1;
}
}
}
return 0;
}
/*我们将每一行看成一个顶点分到集合a，将每一列看成一个顶点分到集合b。(不管是不是泥地)

int main()
{
int i, j, ans = 0;

scanf("%d%d", &n, &m);
for(i = 0; i < n; i++)
scanf("%s", ch[i]);
memset(x, 0, sizeof(x));
memset(y, 0, sizeof(y));
//遍历草图，对每个为‘＊’的点
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
{
if(ch[i][j] == '*')
{
if(j == 0 || ch[i][j-1] == '.')//第一看它的左边是否是连通的泥地，不是就移动到下一个表示该行的点
x[i]++;//x[i]表示第i行第x[i]个点
if(i == 0 || ch[i-1][j] == '.')//第二看它的上边是否是连通的泥地，不是就移动到下一个表示该列的点
y[j]++;//同理y
}
}
memset(match, -1, sizeof(match));//接下来就是普通的二分图了
for(i = 1; i <= n*m; i++)
{
memset(used, 0, sizeof(used));
if(dfs(i))
ans++;
}
printf("%d\n", ans);
return 0;
}```

Followed by: