[ 登录注册 ]

Java

hdu 1507 Uncle Tom's Inherited Land* (二分匹配)

2016-08-24 13:12:17 admin 返回上一页

题目有指出 ( (N x M) - K <= 50), 所以最多也就 50 个点. 然后遍历图上

每一个可行点点, 把它和他 上下左右的可行点连边, 最后就得到了一个二分图, 然后直接

最大匹配, 不过结果有问题, 分析不透彻, 出现了重边. 再 分析下, 因为相邻块之间的下标

和存在奇偶关系, 所以只取 偶数 或 奇数点 建图就行了.

[csharp] 
#include"stdio.h" 
#include"string.h" 
#define N 110 
struct node 

    int x,y; 
}aa[51]; 
int hash[N][N],a[N][N]; 
int map[N][N],v[N],mark[N]; 
int n,m,cnt; 
int dx[4]={1,-1,0,0}; 
int dy[4]={0,0,1,-1}; 
void get_map() 

    int i,j,k,x,y; 
    scanf("%d",&k); 
    memset(hash,0,sizeof(hash)); 
    while(k--) 
    { 
        scanf("%d%d",&x,&y); 
        hash[x][y]=1; 
    } 
    cnt=1; 
    for(i=1;i<=n;i++) 
    { 
        for(j=1;j<=m;j++) 
            if(hash[i][j]==0) 
            { 
                a[i][j]=cnt; 
                aa[cnt].x=i; 
                aa[cnt].y=j; 
                cnt++; 
            } 
    } 
    memset(map,0,sizeof(map)); 
    for(i=1;i<=n;i++) 
    { 
        for(j=1;j<=m;j++) 
            if(hash[i][j]==0) 
            { 
                for(k=0;k<4;k++) 
                { 
                    x=i+dx[k]; 
                    y=j+dy[k]; 
                    if(x>=1&&x<=n&&y>=1&&y<=m&&hash[x][y]==0) 
                    { 
                        map[a[i][j]][a[x][y]]=1; 
                        map[a[x][y]][a[i][j]]=1; 
                    } 
                } 
            } 
    } 

int dfs(int k) 

    int i; 
    for(i=1;i<cnt;i++) 
    { 
        if((aa[i].x+aa[i].y)%2==1) 
            continue; 
        if(map[k][i]&&!v[i]) 
        { 
            v[i]=1; 
            if(mark[i]==-1||dfs(mark[i])) 
            { 
                mark[i]=k; 
                return 1; 
            } 
        } 
    } 
    return 0; 

void output() 

    int i; 
    for(i=1;i<cnt;i++) 
        if(mark[i]!=-1) 
        printf("(%d,%d)--(%d,%d)\n",aa[i].x,aa[i].y,aa[mark[i]].x,aa[mark[i]].y); 

void solve() 

    int i,count; 
    count=0; 
    memset(mark,-1,sizeof(mark)); 
    for(i=1;i<cnt;i++) 
    { 
        if((aa[i].x+aa[i].y)%2==0) 
            continue; 
        memset(v,0,sizeof(v)); 
        if(dfs(i)) www.2cto.com
            count++; 
    } 
    printf("%d\n",count); 
    output(); 
    printf("\n"); 

int main() 

    while(scanf("%d%d",&n,&m)!=-1) 
    { 
        if(!n&&!m) 
            break; 
        get_map(); 
        solve(); 
    } 
    return 0; 


作者:yyf573462811
点击复制链接 与好友分享!回本站首页

文章来源:http://www.bozhiyue.com/java/2016/0824/426400.html
返回上一页    返回分类 上一篇:   下一篇:
相关