LA 6811Irrigation Lines（二部圖，最小點覆蓋）

LA 6811Irrigation Lines（二部圖，最小點覆蓋）

6811 - Irrigation Lines

題目大意：

矩形的農田，每行每列都有一個閘門，一些格子內中有莊稼，問最少開幾個閥門，使得所有的莊稼都能得到灌溉。

解題思路：

明顯的二部圖最小點覆蓋模型。基本屬於二部圖最大匹配的模板題。將行最為一個集合，列作為一個集合，莊稼（即行與列的交叉點）作為關系連邊，問題轉化為，同最少幾個點（行或列），覆蓋所有的邊（莊稼），即最小點覆蓋。

用匈牙利算法即可。

參考代碼：

#include 
#include 
#include 
using namespace std;

const int MAXN = 110;
char graph[MAXN][MAXN];
bool visited[MAXN];
int nCase, cCase, use[MAXN], m, n;

void init() {
    memset(use, -1, sizeof(use));
}

void input() {
    scanf("%d%d", &m, &n);
    for (int i = 0; i < m; i++) {
        scanf("%s", graph[i]);
    }
}

bool find(int x) {
    for (int j = 0; j < n; j++) {
        if (graph[x][j] == '1' && !visited[j]) {
            visited[j] = true;

            if (use[j] == -1 || find(use[j])) {
                use[j] = x;
                return true;
            }
        }
    }
    return false;
}

int match() {
    int count = 0;
    for (int i = 0; i < m; i++) {
        memset(visited, false, sizeof(visited));
        if (find(i)) count++;
    }
    return count;
}

void solve() {
    printf("Case #%d: %d\n", ++cCase, match());
}

int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();

    }
    return 0;
}