Technologieaustausch

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

Fragenlink

  Bei dieser Frage handelt es sich um eine Frage der Shanghai-Abteilung des ICPC Asian Regional Competition 2009.

Bedeutung der Frage

Es gibt eine Möglichkeit, bei einer Blumenschau n Blumen in einem Rechteck mit m Zeilen und n Spalten (m≤n) zu platzieren. Die in den n Zellen jeder Reihe platzierten Blumen unterscheiden sich voneinander und die in den m platzierten Blumen Die Zellen in jeder Spalte unterscheiden sich auch voneinander. Jetzt möchte ich gemäß dieser Regel eine weitere Reihe von Blumen hinzufügen und den k-ten Plan in der Wörterbuchreihenfolge ausgeben. Wenn der k-te Plan nicht existiert, wird -1 ≤ N ≤ M ≤ N, 1 ausgegeben ≤K≤ 200.

analysieren

Bipartite Graph + DFS-Aufzählungsbereinigung, die Idee stammt aus diesem ArtikelBlog。

Finden Sie die Anzahl der Blumen, die in jeder Spalte platziert werden können, verbinden Sie die Kanten und führen Sie dann einen zweiteiligen Diagrammabgleich durch, um zu sehen, ob sie perfekt übereinstimmen können. Wenn nicht, bedeutet dies, dass sie nicht platziert werden können. Das Ausführen dieses zweiteiligen Graphenvergleichs ist nicht umsonst, er wird später verwendet.
Da wir die k-te Wörterbuchreihenfolge benötigen, müssen wir die Blumen aufzählen, die in jeder Spalte platziert werden können. Hier ist eine Beschneidung erforderlich. Wenn die aktuelle Aufzählungsspalte die j-te Spalte ist und die nachfolgenden j+1 bis N-ten Spalten nicht übereinstimmen können, können sie beschnitten werden.

AC-Code

#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