程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> POJ 2446 Chessboard(二分圖匹配)

POJ 2446 Chessboard(二分圖匹配)

編輯:C++入門知識

POJ 2446 Chessboard(二分圖匹配)


題意:給你一個n*m的棋盤, 上面有一些洞洞,要求放置若干1*2的木板, 洞洞位置不能放置, 其他位置要全部覆蓋, 任意一個格子不能同時覆蓋兩塊木板, 求能否完全覆蓋。

思路:二分圖匹配。 相鄰兩個格子, 行數 + 列數 一定是一個奇數一個偶數, 由此將格子分成兩派, 匹配即可。 可以用最大流, 但是匈牙利算法更快, 而且代碼短。

細節參見代碼:

 

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 1500;
int T,n,m,k;
vector g[maxn];
int from[maxn], tot, x, y;
bool use[maxn];
bool match(int x) {
    int len = g[x].size();
    for(int i = 0; i < len; i++)
    if(!use[g[x][i]]) {
        use[g[x][i]] = true;
        if(from[g[x][i]] == -1 || match(from[g[x][i]])) {
            from[g[x][i]] = x;
            return true;
        }
    }
    return false;
}
int hungary(int n) {
    tot = 0;
    memset(from, -1, sizeof(from));
    for(int i = 1; i <= n; i++) {
        memset(use, 0, sizeof(use));
        if(match(i)) ++tot;
    }
    return tot;
}

int getid(int r, int c) {
    return (r - 1) * m + c;
}
bool vis[55][55];
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int main() {
    while(~scanf("%d%d%d",&n,&m,&k)) {
        memset(vis, false, sizeof(vis));
        for(int i = 0; i < k; i++) {
            scanf("%d%d",&x,&y);
            vis[y][x] = true;
        }
        int res = n * m - k;
        if(res & 1) {
            printf("NO\n");
            continue;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(vis[i][j]) continue;
                int id1 = getid(i, j);
                if((i + j) & 1) continue;
                for(int l = 0; l < 4; l++) {
                    int x = i + dx[l];
                    int y = j + dy[l];
                    if(x < 1 || x > n || y < 1 || y > m || vis[x][y]) continue;
                    int id2 = getid(x, y);
                    g[id1].push_back(id2);
                }
            }
        }
        int ans = hungary(n * m);
        if(ans == res / 2) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved