| ||||||||||
| 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 | |||||||||
看到网上题解都是千篇一律,说说我的建图,赋AC代码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 head[MAXM], match[MAXM], used[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;
a[cnt].next = head[u];
head[u] = cnt++;
}
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。(不管是不是泥地)
接下来,假设我们将a中的每个顶点拆成c份(就是列的个数,这c个都表示该行),将b中每个顶点拆成r份(就是行的个数)。(其实不用那么多)*/
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(head, -1, sizeof(head));
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
add(i*m+x[i], j*n+y[j], 1);//在第i行和第j列建立一条边
}
}
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: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator