首页 > 编程语言 > 详细

二分图——poj2446匈牙利算法

时间:2019-05-18 00:10:58      阅读:118      评论:0      收藏:0      [点我收藏+]
/*
怎么建图:
首先分集合:不能相连的点必然在一个集合里,即对角点 
再确定怎么连边: 一个点可以向上下左右连边,如果遇到了洞则不行 

dfs(i),让匹配到的点接受i作为match结果
寻找增广路时,要让v接受i,那么v原来接受的点match[v]就要重新找一个点进行匹配 
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 2500

int n,m,k,hole[100][100],mp[maxn][maxn],id[maxn][maxn];

int vis[maxn],cnt,match[maxn];
int dfs(int x){
    for(int i=1;i<=cnt;i++)
        if(mp[x][i] && !vis[i]){
            vis[i]=1;
            if(!match[i] || dfs(match[i])){//寻找增广路 
                match[i]=x;return 1;
            }
        }
    return 0;
}
void init(){
    cnt=0;
    memset(match,0,sizeof match);
    memset(hole,0,sizeof hole);
    memset(mp,0,sizeof mp);
    memset(id,0,sizeof id);
}
int main(){
    init();
    cin>>m>>n>>k;
    for(int i=1;i<=k;i++){
        int x,y;
        cin>>x>>y;
        hole[y][x]=1;
    }
    //给每个点重定义标记 
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(!hole[i][j])id[i][j]=++cnt; 
    //建图 
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(!hole[i][j])    {
                if(i-1>=1 && !hole[i-1][j])
                    mp[id[i][j]][id[i-1][j]]=1;
                if(i+1<=m && !hole[i+1][j])
                    mp[id[i][j]][id[i+1][j]]=1;
                if(j-1>=1 && !hole[i][j-1])
                    mp[id[i][j]][id[i][j-1]]=1;
                if(j+1<=n && !hole[i][j+1])
                    mp[id[i][j]][id[i][j+1]]=1;
            }
    int ans=0;
    for(int i=1;i<=cnt;i++){
        memset(vis,0,sizeof vis);
        if(dfs(i))++ans;
    }
    if(ans==cnt)puts("YES");
    else puts("NO");
} 

 

二分图——poj2446匈牙利算法

原文:https://www.cnblogs.com/zsben991126/p/10884243.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!