BZOJ 1059（二分图匹配）

要点

发现每行每列都得有1
发现无论怎么换，在同一行的永远在同一行，同一列的永远在同一列
于是换行貌似没什么用啊，换列就够了。换列无法做到则无答案
于是变成了行与列进行二分匹配

#include <cstdio>

#include <cstring>

int T, n, a[205][205];

int match[205], vis[205];

bool dfs(int x) {

    for (int i = 1; i <= n; i++)

        if (!vis[i] && a[x][i]) {

            vis[i] = 1;

            if (!match[i] || dfs(match[i])) {

                match[i] = x; return 1;

            }

        }

    return 0;

}

bool Solve() {

    memset(match, 0, sizeof match);

    for (int i = 1; i <= n; i++) {

        memset(vis, 0, sizeof vis);

        if (!dfs(i))   return 0;

    }

    return 1;

}

int main() {

    for (scanf("%d", &T); T; T--) {

        scanf("%d", &n);

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= n; j++)

                scanf("%d", &a[i][j]);

        puts(Solve() ? "Yes" : "No");

    }

}

巴特西

BZOJ 1059（二分图匹配）

要点

最新文章

热门文章