现在的位置: 首页 > 综合 > 正文

POJ 2446 Chessboard (二分匹配)

2013年08月29日 ⁄ 综合 ⁄ 共 1034字 ⁄ 字号 评论关闭

这道题wa了三次很可惜,其实很简单!

第一次是RE,32*32=1024,好丢人!

第二次是没注意,(x,y)表示y行x列,直接按照原有经验,搞成了x行y列!丢人!

第三次是双层for循环,j的那个内层循环只循环到n结束,正确的是应该到m结束!

这篇总结必然好好保存,写代码真的要认真!

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 1100;
int n, m, k;
int g[35][35];
int cy[N], bmap[N][N];
bool vis[N];

bool dfs( int u ) 
{
    for ( int v = 0; v < n*m; ++v ) if ( !vis[v] && bmap[u][v] ) {
        vis[v] = 1;
        if ( cy[v] == -1 || dfs( cy[v] ) ) {
            cy[v] = u;
            return 1;
        }
    }
    return 0;
}
int match()
{
    int res = 0; 
    memset( cy, -1, sizeof(cy) );
    for ( int i = 0; i < n*m; ++i ) {
        memset( vis, 0, sizeof(vis));
        if ( dfs(i) ) res++;
    }
    return res;
}
int main()
{
    while ( scanf("%d%d%d", &n, &m, &k) == 3 ) {
        memset( g, 0, sizeof(g) );
        memset( bmap, 0, sizeof(bmap) );
        int  num = n*m;
        while ( k-- ) {
            int u, v;
            scanf("%d%d", &u, &v);
            u--, v--;
            g[v][u] = 1;
            num--;
        }
        for ( int i = 0; i < n; ++i ) 
            for ( int j = 0; j < m; ++j ) {
                int u = i*m+j, v;
                if ( g[i][j] == 1 ) continue;
                if ( i > 0 && g[i-1][j] == 0 ) bmap[u][(i-1)*m+j] = 1;
                if ( j > 0 && g[i][j-1] == 0 ) bmap[u][i*m+j-1] = 1;
                if ( j < m-1 && g[i][j+1] == 0 ) bmap[u][i*m+j+1] = 1;
                if ( i < n-1 && g[i+1][j] == 0 ) bmap[u][(i+1)*m+j] = 1;
            }
        int ans = match();
        //printf("%d", ans);
        if ( ans == num ) printf("YES\n");
        else printf("NO\n");
    }
} 

抱歉!评论已关闭.