Compartir tecnología

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

Enlace de pregunta

  Esta pregunta es una pregunta de la División de Shanghai de la Competencia Regional Asiática del ICPC 2009.

Significado de la pregunta

Hay una manera de colocar n flores en un rectángulo con m filas y n columnas (m≤n) en una exposición floral. Las flores colocadas en las n celdas de cada fila son diferentes entre sí y las flores colocadas en las m. Las celdas de cada columna también son diferentes entre sí. Ahora quiero agregar otra fila de flores de acuerdo con esta regla y generar el k-ésimo plan de disposición razonable en el orden del diccionario. Cuando el k-ésimo plan no existe, generar -1. ≤K≤ 200.

analizar

Gráfico bipartito + poda de enumeración dfs, la idea proviene de este artículoBlog。

Encuentre los números de las flores que se pueden colocar en cada columna, conecte los bordes y luego ejecute un gráfico bipartito para ver si pueden coincidir perfectamente. Si no, significa que no se pueden colocar. Ejecutar esta coincidencia de gráficos bipartitos no es en vano, se usará más adelante.
Debido a que necesitamos el orden del diccionario k-ésimo, debemos enumerar las flores que se pueden colocar en cada columna. Aquí se necesita una poda. Si la columna enumerada actual es la j-ésima columna y las siguientes columnas j+1 a N-ésima no pueden coincidir, entonces se pueden podar.

código de CA

#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