poj 2446 Chessboard (匈牙利算法)

Posted by 111qqz on Thursday, May 26, 2016

TOC

poj 2446 题目链接 题意:一个nm的矩形方格里,有k个坏点,然后问能否用12的矩形块将矩形方格填满。坏点不能填,小的矩形块不能重叠,不能超出边界。不能有好点没有被填。

思路:乍一看没什么好的思路。。。然后发现小的矩形块只能有两种放置方法(横着放,竖着放) 可能我们对于第i个,可以横着放,也可以竖着放,但是可能某种方案使得后面的某一块没办法放置,因此我们需要反过来调整第i块的放法。  这个过程似乎和二分图匹配有点类似。。?  那到底有没有相似点呢。。。又如何划分集合呢。。。?

如果每个小方格看做点,能不能填满,其实就等价与这些点的最大匹配数×2+坏点数=mn是否成立。。。那如何划分集合呢。。。? 我们可以根据点的坐标的奇偶性划分集合。。。因为小矩形块是21的,所以容易知道,每块矩形块放置的两个点一定属于不同的集合。。这样就满足了二分图匹配问题的模型。。。

然后匈牙利搞之。

这题一开始WA了。。WA在没有注意到一个小细节,使得连边的时候,有的是左点指向右点,而有的连成了右点指向左点。

/* ***********************************************
Author :111qqz
Created Time :2016年05月25日 星期三 20时19分04秒
File Name :code/poj/2446.cpp
************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N = 40;
int n,m,k;
bool hole[N][N];
int f1[N][N],f2[N][N];
int tot1,tot2;
int head[N*N*2];
int cnt;
bool vis[N*N*2];
int link[N*N*2];
struct Edge
{
    int v;
    int nxt;
}edge[2*N*N];
void addedge( int u,int v)
{
    edge[cnt].v = v;
    edge[cnt].nxt = head[u];
    head[u] = cnt;
    cnt++;
}

bool dfs( int u)
{
    for ( int i = head[u] ; i!=-1 ; i = edge[i].nxt)
    {
    int v = edge[i].v;
    if (vis[v]) continue;
    vis[v] = true;
    if (link[v]==-1||dfs(link[v]))
    {
        link[v] = u;
        return true;
    }
    }
    return false;
}

int hung()
{
    ms(link,-1);
    int res = 0;
    for ( int i = 1 ; i <= tot1 ; i++)
    {
    ms(vis,false);
    if (dfs(i)) res++;
    }

    return res; //无相边/2,一对匹配占两个格子,×2,抵消了。。

}
int main()
{
    #ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
  #endif
    scanf("%d%d%d",&n,&m,&k);
    ms(hole,false);
    ms(head,-1);
    for ( int i = 1 ; i <= k ; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        swap(x,y);
        hole[x][y] = true;
    }
	
    if ((n*m-k)%2==1)
    {
        puts("NO");
        return 0;
    }
    tot1 =  tot2 = 0 ;                       //根据奇偶性划分集合。
    for ( int i = 1 ; i <= n ; i++)
        for ( int j = 1 ; j <= m ; j++)
        if (!hole[i][j])
        {
            if ((i+j)%2==0)
            {
            f1[i][j]=++tot1;
            }
            else
            {
            f2[i][j]=++tot2;
            }
        }
	
    cnt = 0 ;
    for ( int i = 1 ; i <= n ; i++)
        for ( int j = 1 ; j <= m ; j++)
        {
        if (!hole[i][j]&&j+1<=m&&!hole[i][j+1])
        {
            int u = (i+j)%2==0?f1[i][j]:f2[i][j];
            int v = (i+j+1)%2==0?f1[i][j+1]:f2[i][j+1];
            if ((i+j)%2==1) swap(u,v);
            addedge(u,v);  // 保证是f1的点连向f2的点。
          //  addedge(v,u);
        }
        if (!hole[i][j]&&i+1<=n&&!hole[i+1][j])
        {
            int u = (i+j)%2==0?f1[i][j]:f2[i][j];
            int v = (i+j+1)%2==0?f1[i+1][j]:f2[i+1][j];
            if ((i+j)%2==1) swap(u,v); 
            addedge(u,v);  //无向图
          //  addedge(v,u);
        }
        }

    int ans = hung();
//	cout<<"ans:"<<ans<<endl;
    if (ans*2+k==m*n)
    {
        puts("YES");
    }
    else
    {
        puts("NO");
    }

  #ifndef ONLINE_JUDGE  
  fclose(stdin);
  #endif
    return 0;
}

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付