hdoj1045 Fire Net（二分圖最大匹配）

題意：給出一個圖，其中有 . 和 X 兩種，. 為通路，X表示墻，在其中放炸彈，然后炸彈不能穿過墻，問你最多在圖中可以放多少個炸彈？

?

這個題建圖有點復雜orz。

建圖，首先把每一行中的可以放一個炸彈的一塊區域標記為同一個數字，數字不重復，然后列做相同的處理，即縮點！

縮點之后原圖矩陣中每個點都對用一個行數字和一個列數字，然后按照這兩個數字進行二分匹配，其相同值只取一個，得到的結果就是ans。

#include<iostream>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 10
using namespace std;
int n;
int cnt_row,cnt_col;
char map[maxn][maxn];
int line[maxn][maxn],row[maxn][maxn],col[maxn][maxn],match[maxn],used[maxn];
int dfs(int x){
    for (int i=0;i<cnt_col;i++){
        if (line[x][i]==1 && !used[i]){
            used[i]=1;
            if (match[i]==-1 || dfs(match[i])){
                match[i]=x;
                return 1;
            }
        }
    }
    return 0;
}
int main(){
    while (cin >> n && n){
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                cin >> map[i][j];
            }
        }
        memset(row,-1,sizeof(row));
        memset(col,-1,sizeof(col));
        cnt_row=0,cnt_col=0;
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (map[i][j]=='.' && row[i][j]==-1){
                    for (int k=j;map[i][k]=='.' && k<n;k++) row[i][k]=cnt_row;
                    cnt_row++;
                }
                if (map[j][i]=='.' && col[j][i]==-1){
                    for (int k=j;map[k][i]=='.' && k<n;k++) col[k][i]=cnt_col;
                    cnt_col++;
                }
            }
        }
        memset(line,0,sizeof(line));
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (map[i][j]=='.' && row[i][j]!=-1 && col[i][j]!=-1) 
                    line[row[i][j]][col[i][j]]=1;
            }
        }
        int ans=0;
        memset(match,-1,sizeof(match));
        for (int i=0;i<cnt_row;i++){
                memset(used,0,sizeof(used));
                if (dfs(i)) ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

?