376. Tâches mécaniques

Il y a deux machines A,B Et K Tâches.

Machines A Oui. N Différents modèles（Mode 0∼N−1）,Machines B Oui. M Différents modèles（Mode 0∼M−1）.

Les deux machines sont initialement en mode 0.

Chaque tâche peut être exécutée A Exécution supérieure,On peut aussi B Exécution supérieure.

Pour chaque tâche i,Donner deux entiers a[i] Et b[i],Indique si la tâche A Exécution supérieure,Le mode doit être défini à a[i],Si dans B Exécution supérieure,Le mode requis est b[i].

Les tâches peuvent être exécutées dans n'importe quel ordre,Mais chaque machine doit être redémarrée une fois qu'elle change de mode.

Comment répartir les tâches et les séquences,Permet un redémarrage minimal de la machine.

Format d'entrée

L'entrée contient plusieurs ensembles de données d'essai.

La première ligne de chaque ensemble de données contient trois entiers N,M,K.

Et puis... K D'accord,Trois entiers par ligne i,a[i] Et b[i],i Numéro de la tâche,De 0 C'est parti..

Quand vous saisissez un comportement 0 Heure,Indique que l'entrée est terminée.

Format de sortie

Sortie d'un entier par ensemble de données,Indique le nombre minimum de redémarrages requis de la machine,Chaque résultat représente une ligne.

Champ d'application des données

N,M<100,K<1000
0≤a[i]<N
0≤b[i]<M

Exemple d'entrée：

5 5 10
0 1 1
1 1 2
2 1 3
3 1 4
4 2 1
5 2 2
6 2 3
7 2 4
8 3 3
9 4 3
0

Exemple de sortie：

3

Idées：

/* 3 Couverture minimale des points、Ensemble autonome maximum、 Couverture minimale du point de cheminement ( Couverture minimale du point de répétition du chemin ) Nombre maximum de correspondances = Couverture minimale des points = Nombre total de points - Ensemble autonome maximum = Nombre total de points - Couverture minimale du chemin Ça correspond/Faire correspondre les bords:  Un bord qui n'a pas de noeud commun avec d'autres bords ,  On appelle ça une correspondance /Faire correspondre les bords. Points de correspondance:  Faire correspondre les points sur les bords  Points non appariés:  Un point qui n'est pas sur le bord correspondant  Bords non appariés:  Le bord entre deux points de l'image n'est pas un bord correspondant  Correspondance maximale( Nombre maximum de bords correspondants ):  Combien de côtés au plus ,  De sorte que tous les bords n'aient pas de points communs  Zengguang Road(Diamètre):  Un chemin alternatif entre un bord non apparié d'un côté et un bord apparié de l'autre. . Populaire: Commencez par un Vertex non apparié , Après plusieurs sommets correspondants , Dernier chemin vers un Vertex non apparié de la collection opposée , C'est - à - dire que ce chemin relie deux sommets non appariés de deux ensembles différents à travers une série de sommets appariés . Initial: Le bord correspondant est un fil (-), Les bords non appariés sont deux lignes (--) 1 o - o 2 \/ /\ 3 o o 4 En ce moment3->2->1->4Un seul.  Points sur les bords non appariés 3-> Points sur les bords non appariés 4La voie de l'élargissement  Ce chemin d'extension permet de 3-2Ça correspond,1-4 Correspondance pour une correspondance maximale  ( Il n'y a qu'un seul chemin d'expansion pour plus d'appariements , Correspondance maximale <=> Il n'y a pas de chemin d'extension) Problème de couverture minimale Définition:  Donne - nous une image ,  Choisissez le point le plus bas parmi ,  De sorte qu'au moins un Vertex de chaque côté du graphique soit sélectionné   Trois bords assortis  = 1(\),2(\),3(-) o o \1 o .  Choisissez le moins de points (Marqué comme".")  De sorte qu'au moins un des deux points de chaque côté soit sélectionné  / / o o \2 o . . ——3o \ \ o Dans un diagramme bipartite Couverture minimale des points==Nombre maximum de correspondances CarteA = B  Couverture minimale requise A ≥ Nombre maximum de correspondancesB - Correspondance maximalem- Minimum à choisir m Un point pour couvrir mUn côté.( Il n'y a pas d'intersection entre les deux ) Nombre maximum de correspondancesB = Couverture minimale des pointsA Le signe égal peut être établi  -  Construire un schéma  -- Comme la couverture minimale des points est la valeur minimale de tous les scénarios  Structure: 1 Trouver la correspondance maximale(Hongrie) 2  Chaque point non apparié de gauche {a,b}On y va.  Faites un agrandissement à droite. ( Deux lignes horizontales pointillées - -) o o \ ao - -. / / o o \ bo - -. . —— o \ \ o 3  Marquer tous les points passés  Marqué comme.  Et le point qui n'est pas passé est toujours o . o \ -> e1 a.- -.3 / / . o \ -> e2 b.- -.2 1. —— o -> e3 \ \ oc  Tous les points non marqués à gauche {1} Et tous les points marqués à droite {2,3} 1  Tous les points non appariés à gauche doivent être marqués ( Ce sont les points de départ ) /  Les points non marqués à gauche doivent correspondre (1) 2  Tous les points non appariés à droite ne doivent pas être marqués ( Sinon, il y aura un élargissement ) /  Tous les points marqués à droite doivent correspondre (2,3)  Examen de la définition de la route élargie : Non - correspondance à gauche -> Chemin du point non apparié à droite   Et marqué pour aller du point non apparié gauche au point non apparié droit  3  Pour les bords correspondants   Soit les points gauche et droit sont marqués en même temps   Ou ne pas être marqué en même temps ( Parce que dans la recherche d'un chemin plus large , Le point de correspondance gauche ne peut être atteint que par le côté droit .)  Un seul point doit être sélectionné pour chaque bord correspondant  -  Sélectionnez le point marqué à droite {2,3}/ Sélectionnez les points non marqués à gauche {1} En ce moment: Le point que nous avons choisi (.)Nombre de==Nombre de correspondances(e1、e2、e3) 0  Définissez d'abord les hypothèses actuelles de satisfaction : À gauche et à droite, les bords correspondants doivent être couverts par les bords correspondants dans l'arbre de correspondance maximum.   Si les bords des points non appariés sont écrasés par les bords appariés dans le nombre maximum de correspondances ？ 1  Non - correspondance à gauche i →  Point de correspondance à droite j (Ruedgea-3,Edgeb-2) Parce quei C'est le point de départ ,Alors...j Ça doit être marqué . Et nous avons choisi tous les points marqués à droite (Division), Donc ces bords sont aussi couverts . 2  Point de correspondance à gauche i →  Non - correspondance à droite j(Ruedge1-c  Non - correspondance à droite == Points non marqués ) i Ça ne doit pas être marqué , Sinon, on repart à j J'ai trouvé le chemin de l'élargissement . Et nous avons choisi tous les points non marqués à gauche (Division), Donc ces bords sont aussi couverts . Dessinez.i L'exemple marqué explique pourquoi  0.-- . -> Les points marqués sont des points qui ne correspondent pas à gauche 0On y va.i Marque après iDe / Si vous pouviezi->j, Ça veut dire trouver un 0-jLe chemin de l'élargissement, Il peut y avoir plus d'un bord correspondant  /  Contradiction avec la correspondance maximale  i.—— o \ \ o j 3  Ni à gauche ni à droite ne correspondent ( Vous pouvez ajouter un nouveau bord à la correspondance maximale ) --  C'est en contradiction avec la correspondance actuelle, qui est la plus grande correspondance  Donc,  Ce que nous avons construit, c'est que 3 Points et Max 3 Les bords correspondants couvrent  */

Code：

/* La question a[i]=0 || b[i]=0On peut sauter Une missioniPeut êtreA、B Les deux états de la machine a[i]、b[i]Terminé., Voir une tâche comme un bord , Les deux états sont considérés comme deux paramètres ,  Pour accomplir une tâche, sélectionnez un des deux points (Les tâches peuvent être effectuéesA L'exécution peut également être effectuée sur BExécution supérieure),  Pour toutes les tâches à partir de N+M-2En un point( Ne contient pas de 0Statut) Choisissez le moins de points ,Couvrir tous les bords(Mission),  Le problème est de trouver la couverture minimale ( La couverture minimale du point dans le graphique bipartite est équivalente au nombre maximal de correspondances --Algorithme hongrois). */


#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, k;
int match[N];
bool g[N][N], st[N];

bool find(int x)
{
    
    for (int i = 1; i < m; i++)
    {
    
        if (!st[i] && g[x][i])
        {
    
            st[i] = 1;
            if (match[i] == -1 || find(match[i]))
            {
    
                match[i] = x;
                return true;
            }
        }
    }

    return false;
}

int main()
{
    
    while (cin >> n, n)
    {
    
        cin >> m >> k;
        memset(g, 0, sizeof g);
        memset(match, -1, sizeof match);
        while (k--)
        {
    
            int t, a, b;
            cin >> t >> a >> b;
            if (!a || !b)
                continue;
            g[a][b] = true;
        }

        int res = 0;
        for (int i = 1; i < n; i++)
        {
    
            memset(st, 0, sizeof st);
            // À l'heure actuellei Ça doit être sans objet 
            if (find(i))
                res++;
        }
        cout << res << endl;
    }

    return 0;
}