Обмен технологиями

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

Ссылка на вопрос

  Это вопрос от Шанхайского дивизиона Азиатских региональных соревнований ICPC 2009 года.

Значение вопроса

Существует способ разместить n цветов в прямоугольнике с m строками и n столбцами (m≤n) на выставке цветов. Цветы, помещенные в n ячеек в каждом ряду, отличаются друг от друга, а цветы, размещенные в m. ячейки в каждом столбце также отличаются друг от друга. Теперь я хочу добавить еще один ряд цветов в соответствии с этим правилом и вывести k-й план разумного расположения в словарном порядке. Если k-й план не существует, выведите -1≤N≤200,0≤M≤N,1. ≤К≤ 200.

анализировать

Двудольный граф + сокращение перечисления dfs, идея взята из этой статьиблог。

Найдите количество цветов, которые можно поместить в каждый столбец, соедините ребра, а затем запустите сопоставление двудольного графика, чтобы проверить, могут ли они совпадать идеально. Если нет, это означает, что их невозможно разместить. Запуск этого сопоставления двудольного графа не напрасный, он будет использован позже.
Поскольку нам нужен k-й порядок словаря, нам нужно перечислить цветы, которые можно разместить в каждом столбце. Здесь необходимо сокращение. Если текущий нумерованный столбец является j-м столбцом, а последующие столбцы от j+1 до N не могут быть сопоставлены, то их можно сократить.

Код переменного тока

#include <iostream>
#include <cstring>
using namespace std;

#define N 205
int g[N][N], f[N][N], c[N], px[N], py[N], vis[N], ans[N], p1[N], p2[N], m, n, k, clk; bool use[N];

bool dfs(int u, int pos = -1) {
    if (u <= pos) return false;
    vis[u] = clk;
    for (int i=0, v; i<c[u]; ++i) if (py[v = g[u][i]] < 0 || (vis[py[v]]!=clk && dfs(py[v], pos))) {
        px[u] = v; py[v] = u;
        return true;
    }
    return false;
}

int max_match() {
    memset(px, -1, sizeof(px)); memset(py, -1, sizeof(py)); memset(vis, -1, sizeof(vis));
    int cc = 0;
    for (int i=1; i<=n; ++i) if (px[i] < 0 && dfs(clk = i)) ++cc;
    return cc;
}

bool ok(int u, int v) {
    if (px[u] == v) return true;
    int x = 0;
    for (int i=1; i<=n; ++i) {
        p1[i] = px[i]; p2[i] = py[i];
        if (px[i] == v) if ((x = i) < u) return false;
    }
    px[x] = py[px[u]] = -1; px[u] = v; py[v] = u; ++clk;
    if (dfs(x, u)) return true;
    for (int i=1; i<=n; ++i) px[i] = p1[i], py[i] = p2[i];
    return false;
}

bool find(int u) {
    if (u > n) return ++m == k;
    for (int i=0, v; i<c[u]; ++i) if (!use[v = g[u][i]] && ok(u, v)) {
        use[v] = true; ans[u] = v;
        if (find(u+1)) return true;
        use[v] = false;
    }
    return false;
}

void solve () {
    cin >> n >> m >> k;
    for (int i=1; i<=m; ++i) for (int j=1; j<=n; ++j) cin >> f[i][j];
    for (int i=1; i<=n; ++i) {
        memset(vis, c[i] = 0, sizeof(vis));
        for (int j=1; j<=m; ++j) vis[f[j][i]] = true;
        for (int j=1; j<=n; ++j) if (!vis[j]) g[i][c[i]++] = j;
    }
    if (max_match() != n) {
        cout << " -1" << endl;
        return;
    }
    memset(use, m = 0, sizeof(use)); memset(vis, clk = 0, sizeof(vis));
    if (find(1)) {
        for (int i=1; i<=n; ++i) cout << ' ' << ans[i];
        cout << endl;
    } else cout << " -1" << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    for (int k=1; k<=t; ++k) cout << "Case #" << k << ':', solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72