Κοινή χρήση τεχνολογίας

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

Σύνδεσμος ερώτησης

  Αυτή η ερώτηση είναι μια ερώτηση από το Τμήμα Σαγκάης του Ασιατικού Περιφερειακού Διαγωνισμού 2009 ICPC.

Σημασία ερώτησης

Υπάρχει ένας τρόπος να τοποθετήσετε n λουλούδια σε ένα ορθογώνιο με m σειρές και n στήλες (m≤n) σε μια έκθεση λουλουδιών Τα λουλούδια που τοποθετούνται στα n κελιά σε κάθε σειρά είναι διαφορετικά μεταξύ τους και τα λουλούδια που τοποθετούνται στο m Τα κελιά σε κάθε στήλη είναι επίσης διαφορετικά μεταξύ τους. Τώρα θέλω να προσθέσω μια άλλη σειρά λουλουδιών σύμφωνα με αυτόν τον κανόνα και να βγάλω το kth σχέδιο διάταξης με τη σειρά του λεξικού ≤K≤ 200.

αναλύει

Διμερές γράφημα + κλάδεμα απαρίθμησης dfs, η ιδέα προέρχεται από αυτό το άρθροblog。

Βρείτε τους αριθμούς των λουλουδιών που μπορούν να τοποθετηθούν σε κάθε στήλη, συνδέστε τις άκρες και, στη συνέχεια, εκτελέστε ένα διμερές γράφημα που ταιριάζουν για να δείτε αν μπορούν να ταιριάζουν τέλεια. Εάν όχι, σημαίνει ότι δεν μπορούν να τοποθετηθούν. Η εκτέλεση αυτής της διμερούς αντιστοίχισης γραφήματος δεν είναι μάταιη, θα χρησιμοποιηθεί αργότερα.
Επειδή χρειαζόμαστε την k-th σειρά λεξικού, πρέπει να απαριθμήσουμε τα λουλούδια που μπορούν να τοποθετηθούν σε κάθε στήλη. Απαιτείται κλάδεμα εδώ Αν η τρέχουσα απαριθμημένη στήλη είναι η j-η στήλη και οι επόμενες στήλες j+1 με Ν-ες δεν μπορούν να αντιστοιχιστούν, τότε μπορούν να κλαδευτούν.

Κωδικός AC

#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