poj 1315 Don't Get Rooked(二分图)

写了几个小时，终于把这个版本也搞定了。只是建图比较麻烦，搞了70%的时间，先根据横的分成一块一块（g1），再根据竖的分成一块一块（g2），如果g1跟g2中有相交的块就连接。  然后用匈牙利算法模版算最大匹配数就ok了。

这个不好解释，其实我也不太明白为什么可以这么做，反正记得老师教二分匹配的时候就讲过类似题目。

以下是代码：

 

/*二分图（匈牙利算法）版*/

#include <stdio.h>
#include <string.h>
#include <conio.h>

int n, match, count2, count1, max;
int g1[5][5], g2[5][5], g[10][10], used[10], mat[10];

int find(int k)
{
    int i, j;
    for(i=1; i<= count2; i++)
    {
        if(g[k][i] && !used[i])
        {
            used[i] = 1;
            if(mat[i] == 0 || find(mat[i]))
            {
                mat[i] = k;
                return 1;
            }
        }
    }
    return 0;
}

void hungary()
{
    int i;
    memset(mat, 0, sizeof(mat));
    for(i=1; i<=count1; i++)
    {
        if(find(i))
            match++;
        memset(used, 0, sizeof(used));
    }
}

int main()
{
    int i, j, ok;
    char ch;

    freopen("in.txt", "r", stdin);
    
    while(scanf("%d", &n) && n)
    {
        count1 = 0;
        memset(g1, 0, sizeof(g1));
        memset(g2, 0, sizeof(g2));
        ok = 1;
        max = 0;
        for(i=1; i<=n; i++)
        {
            getchar();
            if(ok)
                count1++;
            ok = 0;
            for(j=1; j<=n; j++)
            {
                scanf("%c", & ch);
                if(ch == '.')
                {
                    g1[i][j] = count1;
                    ok = 1;
                }
                if(ch == 'X' && ok)
                {
                    count1++;
                    ok = 0;
                }
            }
        }
        if(!ok)
            count1--;
        max = count1;
        ok = 1;
        count2 = 0;
        for(i=1; i<=n; i++)
        {
            if(ok)
                count2++;
            ok = 0;
            for(j=1; j<=n; j++)
            {
                if(g1[j][i])
                {
                    g2[j][i] = count2;
                    ok = 1;
                }
                else if(ok)
                {
                    ok = 0;    
                    count2++;
                }
            }
        }
        if(!ok)
            count2--;
        max = max > count2 ? max : count2;
        
        memset(g, 0, sizeof(g));
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=n; j++)
            {
                if(g1[i][j] * g2[i][j] && !g[g1[i][j]][g2[i][j]])
                {
                    g[g1[i][j]][g2[i][j]] = 1;
                }
            }
        }
        match = 0;
        hungary();
        printf("%d\n", match);
    }
    getch();
    return 0;
}