प्रौद्योगिकी साझेदारी

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

प्रश्न लिङ्क

  एषः प्रश्नः २००९ तमे वर्षे आईसीपीसी एशियाईक्षेत्रीयप्रतियोगितायाः शाङ्घाईविभागस्य प्रश्नः अस्ति ।

प्रश्नार्थ

पुष्पप्रदर्शने m पङ्क्तिभिः n स्तम्भैः (m≤n) सह आयतायां n पुष्पाणि स्थापयितुं एकः उपायः अस्ति प्रत्येकं पङ्क्तौ n कोष्ठकेषु स्थापितानि पुष्पाणि परस्परं भिन्नानि सन्ति, तथा च m मध्ये स्थापितानि पुष्पाणि प्रत्येकस्मिन् स्तम्भे कोष्ठकाः अपि परस्परं भिन्नाः भवन्ति . अधुना अहम् अस्य नियमस्य अनुसारं पुष्पाणां अन्यां पङ्क्तिं योजयितुम् इच्छामि, तथा च kth उचितव्यवस्थायोजनां शब्दकोशक्रमेण आउटपुट् कर्तुम् इच्छामि यदा kth योजना नास्ति तदा -1 आउटपुट् कुर्वन्तु ≤K≤ 200।

विश्लेषणं कुरुत

द्विपक्षीय आलेख + dfs गणना छंटाई, विचारः अस्मात् लेखात् आगतःblog。

प्रत्येकस्मिन् स्तम्भे स्थापयितुं शक्यमाणानां पुष्पाणां संख्यां ज्ञात्वा किनारेषु संयोजयन्तु, ततः द्विपक्षीयं आलेखं चालयन्तु यत् ते सम्यक् मेलनं कर्तुं शक्नुवन्ति वा इति एतत् द्विपक्षीयं आलेखमेलनं चालयितुं व्यर्थं न भवति, पश्चात् तस्य उपयोगः भविष्यति ।
यतः अस्माकं k-th शब्दकोशक्रमस्य आवश्यकता अस्ति, अतः प्रत्येकस्मिन् स्तम्भे स्थापयितुं शक्यन्ते ये पुष्पाणि तेषां गणना आवश्यकी अस्ति । अत्र छंटनी आवश्यकी अस्ति यदि वर्तमानगणितस्तम्भः j-तमः स्तम्भः अस्ति, तदनन्तरं j+1 तः N-तमं स्तम्भं मेलयितुम् न शक्यते, तर्हि तेषां छंटनी कर्तुं शक्यते ।

एसी कोड

#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