Teknologian jakaminen

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

Kysymys linkki

  Tämä kysymys on vuoden 2009 ICPC:n Aasian aluekilpailun Shanghai-divisioonan kysymys.

Kysymyksen merkitys

Kukkanäyttelyssä on tapa sijoittaa n kukkaa suorakulmioon, jossa on m riviä ja n saraketta (m≤n). Jokaisen rivin n soluun sijoitetut kukat eroavat toisistaan, ja m:ään sijoitetut kukat kunkin sarakkeen solut ovat myös erilaisia. Nyt haluan lisätä toisen rivin kukkia tämän säännön mukaisesti ja tulostaa k:nnen järkevän järjestelysuunnitelman sanakirjan järjestyksessä ≤K≤ 200.

analysoida

Kaksiosainen kaavio + dfs-luettelon karsiminen, idea tulee tästä artikkelistablogi。

Etsi kukkien numerot, jotka voidaan sijoittaa kuhunkin sarakkeeseen, yhdistä reunat ja suorita sitten kaksiosainen kaavio, jotta näet, voivatko ne täsmää täydellisesti. Jos ei, niitä ei voi sijoittaa. Tämän kaksiosaisen graafisovituksen suorittaminen ei ole turhaa, sitä käytetään myöhemmin.
Koska tarvitsemme k:nnen sanakirjan järjestyksen, meidän on lueteltava kukat, jotka voidaan sijoittaa kuhunkin sarakkeeseen. Tässä tarvitaan karsimista, jos nykyinen lueteltu sarake on j:s sarake, eikä myöhempiä sarakkeita j+1:stä N:een voida yhdistää, ne voidaan leikata.

AC koodi

#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