1 条题解

  • 0
    @ 2025-10-8 16:57:15
    #include <bits/stdc++.h>
    using namespace std;
    
    struct edge { int x, y, pre; } a[3000];
    int alen, last[3000];
    
    void ins(int x, int y) {
        ++alen;
        a[alen] = edge{ x, y, last[x] };
        last[x] = alen;
    }
    
    int match[3000], chw[3000], tsp;
    
    bool dfs(int x) {
        for (int k = last[x]; k; k = a[k].pre) {
            int y = a[k].y;
            if (chw[y] != tsp) {
                chw[y] = tsp;
                if (match[y] == 0 || dfs(match[y]) == 1) {
                    match[y] = x;
                    return 1;
                }
            }
        }
        return 0;
    }
    
    char s[60][60];
    int mapx[60][60], mapy[60][60];
    
    int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            scanf("%s", s[i] + 1);
        }
    
        int X = 0, Y = 0;
        for (int i = 1; i <= n; i++) {
            X++;
            for (int j = 1; j <= m; j++) {
                if (s[i][j] == '*') {
                    if (s[i][j - 1] != '*') {
                        X++;
                    }
                    mapx[i][j] = X;
                }
            }
        }
    
        for (int j = 1; j <= m; j++) {
            Y++;
            for (int i = 1; i <= n; i++) {
                if (s[i][j] == '*') {
                    if (s[i - 1][j] != '*') {
                        Y++;
                    }
                    mapy[i][j] = Y;
                }
            }
        }
    
        alen = 0;
        memset(last, 0, sizeof(last));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (s[i][j] == '*') {
                    ins(mapx[i][j], mapy[i][j]);
                }
            }
        }
    
        int ans = 0;
        memset(match, 0, sizeof(match));
        memset(chw, 0, sizeof(chw));
        for (int i = 1; i <= X; i++) {
            tsp = i;
            if (dfs(i)) {
                ans++;
            }
        }
    
        printf("%d\n", ans);
        return 0;
    }
    
    • 1

    *【二分图:最小覆盖】[USACO05JAN] Muddy Fields G

    信息

    ID
    1466
    时间
    1000ms
    内存
    64MiB
    难度
    7
    标签
    递交数
    189
    已通过
    44
    上传者