• Problème de correspondance des pilotes
• Cours
• [USACO05NOV] Astéroïdes G
• [SHOI2002] Bal
• P10945 Placement des robots (double expérience, triple expérience)
• Couverture du plateau d'échecs
• Collecte d'échantillons
• [USACO11NOV] Course de vaches G / Intersection de segments
• [ZJOI2007] Jeu de matrices
• [HNOI2013] Désinfection
• [Équipe nationale d'entraînement] Guerre des clans
• [JSOI2009] Jeu
• [POI2009] Lyz

Problème de correspondance des pilotes

Chaque paire \\(x,y\\) peut être vue comme une arête. Le problème devient un graphe biparti où les pilotes principaux ne peuvent pas être connectés entre eux, et il en va de même pour les copilotes. L'algorithme hongrois est utilisé.

#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 100;
int n, m, match[MAXN], used[MAXN];
vector<int> adj[MAXN];

bool dfs(int u) {
    for(auto &v : adj[u]) {
        if(!used[v]) {
            used[v] = 1;
            if(match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m;
    int x, y;
    while(cin >> x >> y) {
        adj[x].push_back(y);
    }
    int total_matches = 0;
    fill(match, match + MAXN, -1);
    for(int i = 1; i <= n; ++i) {
        fill(used, used + MAXN, 0);
        if(dfs(i)) total_matches++;
    }
    cout << total_matches;
    return 0;
}

Cours

Reliez chaque personne à ses cours disponibles et utilisez l'algorithme hongrois pour trouver la correspondance maximale.

#include<iostream>
#include<vector>
using namespace std;
const int MAXN = 600;
int T, n, m, match[MAXN], used[MAXN];
vector<int> adj[MAXN];

bool dfs(int u) {
    for(auto &v : adj[u]) {
        if(!used[v]) {
            used[v] = 1;
            if(match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> T;
    while(T--) {
        fill(match, match + MAXN, -1);
        fill(adj[0], adj[MAXN], vector<int>());
        cin >> m >> n;
        for(int i = 1; i <= m; ++i) {
            int count;
            cin >> count;
            while(count--) {
                int course;
                cin >> course;
                adj[i].push_back(course);
            }
        }
        int total_matches = 0;
        for(int i = 1; i <= n; ++i) {
            fill(used, used + MAXN, 0);
            if(dfs(i)) total_matches++;
        }
        if(total_matches == m) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

[USACO05NOV] Astéroïdes G

Pour éliminer chaque astéroïde, soit toute la ligne est éliminée, soit toute la colonne. Reliez les lignes aux colonnes et utilisez l'algorithme hongrois.

[SHOI2002] Bal

Connectez les garçons et filles dansant ensemble, et calculez le nombre maximum de paires possibles.

P10945 Placement des robots

Dans ce problème, chaque rangée et colonne sont considérées comme des ensembles distincts. Les espaces libres sont reliés par des arêtes pour maximisre les positions de placement des robots.

Couverture du plateau d'échecs

Utilisez la méthode de coloration bichrome pour relier les cases noires et blanches avec des dominos.

Collecte d'échantillons

Le problème se résume à un graphe orienté acyclique (DAG), où il faut minimiser le nombre de points couverts.

[USACO11NOV] Course de vaches G

Calculez si deux segments s'intersectent et reliez-les par des arêtes pour appliquer l'algorithme de couplage maximal.

[ZJOI2007] Jeu de matrices

Utilisez une stratégie de couplage maximal pour garantir que chaque ligne et colonne contienne au moins un '1'.

[HNOI2013] Désinfection

Utilisez une approche itérative pour tester toutes les possibilités de découpage des dimensions du cube afin de minimiser le coût.

[Équipe nationale d'entraînement] Guerre des clans

Utilisez un modèle de graphe biparti pour résoudre le problème de déplacement des troupes sans boucles.

[JSOI2009] Jeu

Appliquez une stratégie de jeu basée sur la théorie des graphes bipartis et utilisez des DFS pour identifier les positions gagnantes.

[POI2009] Lyz

Appliquez le théorème de Hall pour vérifier les conditions de couplage complet dans un graphe biparti et utilisez une structure de données avancée pour maintenir les intervalles optimaux.