2011-0072

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：
{{{
给定一个n*n的矩阵，矩阵元素只有'U'和'D'两种，可以进行交换行当操作，问能否经过操作使得矩阵对角线元素全部为'U'。
}}}

解法：
{{{
因为若最后能够成功，说明每一行都有一个'U'和每一列对应，这是一个二分匹配模型，如果能够完全匹配那么说明可以达到要求的状态否则不行
}}}

代码：
{{{
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 256;

#define _clr(x) memset(x, 0xff, sizeof(int) * MAXN)

bool mat[MAXN][MAXN];
int m1[MAXN], m2[MAXN];
char s[MAXN];

int gao(int m, int n, const bool mat[][MAXN], int * match1, int * match2) {
    int s[MAXN + 1], t[MAXN], p, q, ret = 0, i, j, k;
    _clr(match1);
    _clr(match2);
    for (i = 0; i < m; ret += (match1[i++] >= 0)) {
        _clr(t);
        for (s[p = q = 0] = i; p <= q && match1[i] < 0; p++) {
            k = s[p];
            for (j = 0; j < n && match1[i] < 0; j++) {
                if (mat[k][j] && t[j] < 0) {
                    s[++q] = match2[j];
                    t[j] = k;
                    if (s[q] < 0) {
                        for (p = j; p >= 0; j = p) {
                            match2[j] = k = t[j];
                            p = match1[k];
                            match1[k] = j;
                        }
                    }
                }
            }
        }
    }
    return ret;
}

int main() {
    int i, j, k;
    while (1 == scanf("%d", &k)) {
        for (i=0; i<k; ++i) {
            scanf("%s", s);
            for (j=0; j<k; ++j) mat[i][j] = s[j] == 'U';
        }
        puts(gao(k, k, mat, m1, m2) == k ? "YES" : "NO");
    }
    return 0;
}
}}}
[by delta_4d]

题意：

给定一个n*n的矩阵，矩阵元素只有'U'和'D'两种，可以进行交换行当操作，问能否经过操作使得矩阵对角线元素全部为'U'。

解法：

因为若最后能够成功，说明每一行都有一个'U'和每一列对应，这是一个二分匹配模型，如果能够完全匹配那么说明可以达到要求的状态否则不行

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 256;
#define _clr(x) memset(x, 0xff, sizeof(int) * MAXN)
bool mat[MAXN][MAXN];
int m1[MAXN], m2[MAXN];
char s[MAXN];
int gao(int m, int n, const bool mat[][MAXN], int * match1, int * match2) {
    int s[MAXN + 1], t[MAXN], p, q, ret = 0, i, j, k;
    _clr(match1);
    _clr(match2);
    for (i = 0; i < m; ret += (match1[i++] >= 0)) {
        _clr(t);
        for (s[p = q = 0] = i; p <= q && match1[i] < 0; p++) {
            k = s[p];
            for (j = 0; j < n && match1[i] < 0; j++) {
                if (mat[k][j] && t[j] < 0) {
                    s[++q] = match2[j];
                    t[j] = k;
                    if (s[q] < 0) {
                        for (p = j; p >= 0; j = p) {
                            match2[j] = k = t[j];
                            p = match1[k];
                            match1[k] = j;
                        }
                    }
                }
            }
        }
    }
    return ret;
}
int main() {
    int i, j, k;
    while (1 == scanf("%d", &k)) {
        for (i=0; i<k; ++i) {
            scanf("%s", s);
            for (j=0; j<k; ++j) mat[i][j] = s[j] == 'U';
        }
        puts(gao(k, k, mat, m1, m2) == k ? "YES" : "NO");
    }
    return 0;
}

[by delta_4d]