Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  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 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator