Partage de technologie

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

Lien vers les questions

  Cette question est une question de la division de Shanghai du concours régional asiatique ICPC 2009.

Signification des questions

Il existe un moyen de placer n fleurs dans un rectangle avec m lignes et n colonnes (m≤n) lors d'une exposition florale. Les fleurs placées dans les n cellules de chaque rangée sont différentes les unes des autres, et les fleurs placées dans les m. les cellules de chaque colonne sont également différentes les unes des autres. Maintenant, je veux ajouter une autre rangée de fleurs selon cette règle et afficher le kème plan d'arrangement raisonnable dans l'ordre du dictionnaire. Lorsque le kème plan n'existe pas, afficher -1≤N≤200,0≤M≤N,1. ≤K≤ 200.

analyser

Graphique bipartite + élagage d'énumération dfs, l'idée vient de cet articleBlog。

Trouvez les numéros des fleurs qui peuvent être placées dans chaque colonne, reliez les bords, puis exécutez une correspondance graphique bipartie pour voir si elles peuvent correspondre parfaitement. Sinon, cela signifie qu'elles ne peuvent pas être placées. L'exécution de cette correspondance de graphes bipartis n'est pas vaine, elle sera utilisée plus tard.
Parce que nous avons besoin du k-ème ordre du dictionnaire, nous devons énumérer les fleurs qui peuvent être placées dans chaque colonne. Un élagage est nécessaire ici. Si la colonne énumérée actuelle est la j-ème colonne et que les j+1 à N-ème colonnes suivantes ne peuvent pas correspondre, elles peuvent alors être élaguées.

Code 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