UVa12668 - Attacking rooks(Maximum Bipartite Matching 二分匹配)

題目大意

給你一個西洋棋盤，會在這個棋盤上放一些小兵，你必須在這個棋盤中放入一些城堡，且保證城堡攻擊範圍不會有另外一個城堡
試問最多可以放幾個

題目連結

重點觀念

• Maximum Bipartite Matching by 大衛的筆記
• 如何將棋盤變成二分圖

分析

• 題目要求為，不讓城堡看到城堡，也就是城堡在的位置\((x,y)\)，其 x 軸與 y 軸都不可以有其他城堡，除非有小兵擋住，那就是一個很明顯的二分圖，x 對 y 二分
• 如果有小兵站在棋盤上，那我們應該要以小兵為分界線，分出兩個 x,y 軸，因為站在小兵兩旁的城堡是合法的
• 再來我們相同的 x,y 軸都設定為同一號碼，不斷進行匹配即可。

參考連結

UVALive 6525 Attacking rooks 二分匹配 经典题 by 九野的博客
UVALive 6525 Attacking rooks(二分图最大匹配) by FDU_Nan

心得

這題我學了好久…，第一次寫到用棋盤來表達二分圖，一開始真的是完全不知道原來這裡要用二分圖阿XDDD，也學到原來可以將二分圖的節點內在放入很多的點，就可以做到讓題目的要求，太神了、太酷了，第一次學到。

希望學起來可以對我的未來有幫助

題目程式碼

有一些程式碼註解在 Maximum Bipartite Matching by 大衛的筆記 請供參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define int long long
#define MAXN 120
using namespace std;
vector<int> edge[MAXN*MAXN];
int graph[MAXN][MAXN];
int mx[MAXN*MAXN], my[MAXN*MAXN], vy[MAXN*MAXN]; //matchX, matchY, visitY
int ex[MAXN][MAXN], ey[MAXN][MAXN]; //edgeX, edgeY
int n, cnt;
string s;

bool dfs(int x){
    for(auto y: edge[x]){
        if(vy[y] == 1) continue;
        vy[y] = 1;
        if(my[y] == -1 || dfs(my[y])){
            mx[x] = y;
            my[y] = x;
            return true;
        }
    }
    return false;
}

int bipartite_matching(){
    memset(mx, -1, sizeof(mx));
    memset(my, -1, sizeof(my));
    int ans = 0;

    for(int i = 1; i <= cnt; i++){
        memset(vy, 0, sizeof(vy));
        if(dfs(i)) ans++;

    }
    return ans;
}

void connect_edge(){ //將棋盤轉換成二分圖的邊
    for(int i = 1; i <= cnt; i++) edge[i].clear();

    int x;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(graph[i][j] == 0){
                x = ex[i][j];
                edge[x].push_back(ey[i][j]); //這個點的相同 x,y 軸，組成一個邊
            }
        }
    }

    return;
}

void print_graph(){ //debug 與方便學習用
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            printf("%2d ", graph[i][j]);
        }
        printf("\n");
    }
}

void print_ex(){ //debug 與方便學習用
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            printf("%2d ", ex[i][j]);
        }
        printf("\n");
    }
}

void print_ey(){ //debug 與方便學習用
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            printf("%2d ", ey[i][j]);
        }
        printf("\n");
    }
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n){
        memset(graph, 0, sizeof(graph)); //清空資料
        memset(ex, 0, sizeof(ex));
        memset(ey, 0, sizeof(ey));

        //如果那一個 row or column 有小兵存在，那分裂後的 x 軸就從 n+1 開始依序 hash
        cnt = n+1; 
        for(int i = 1; i <= n; i++){
            cin >> s;
            s = ' ' + s; //從 index 1 開始
            for(int j = 1; j <= n; j++){
                if(s[j] == 'X') graph[i][j] = cnt++; //表示這邊可以分裂 row and column 
                else graph[i][j] = 0;
            }
        }
        //print_graph();

        //y 軸，從前往後，判斷他們是否屬於同一個 y 軸
        for(int i = 1; i <= n; i++) ey[0][i] = i; 
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                //如果有分裂，那就將 ey 點開始往前都變為新節點
                if(graph[i][j]) ey[i][j] = graph[i][j]; 
                else ey[i][j] = ey[i-1][j];
            }
        }
        //print_ey(); cout << "\n";

        //x 軸，從後往前，判斷他們是否屬於同一個 x 軸
        for(int i = 1; i <= n; i++) ex[i][n+1] = i;
        for(int i = n; i > 0; i--){
            for(int j = 1; j <= n; j++){
                //如果有分裂，那就將 ex 點開始往前都變為新節點
                if(graph[j][i]) ex[j][i] = graph[j][i];
                else ex[j][i] = ex[j][i+1];
            }
        }
        //print_ex();

        connect_edge();
        int ans = bipartite_matching();
        cout << ans << "\n";

    }

    return 0;
}