376. machine tasks

There are two machines A,B as well as K A mission .

machine A Yes N Different models （ Pattern 0∼N−1）, machine B Yes M Different models （ Pattern 0∼M−1）.

Both machines were initially in mode 0.

Each task can be either in A On the implementation , It can also be in B On the implementation .

For each task i, Given two integers a[i] and b[i], If the task is in A On the implementation , You need to set the mode to a[i], If in B On the implementation , The required mode is b[i].

Tasks can be performed in any order , But every time a machine changes mode, it needs to be restarted .

Find out how to assign tasks and arrange them in a reasonable order , It can minimize the number of machine restarts .

Input format

Input contains multiple sets of test data .

The first row of each set of data contains three integers N,M,K.

Next K That's ok , Three integers per row i,a[i] and b[i],i Number the task , from 0 Start .

When entering a behavior 0 when , Indicates that the input is terminated .

Output format

Output an integer for each group of data , Indicates the minimum number of machine restarts required , Each result takes up one line .

Data range

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

sample input ：

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

sample output ：

3

Ideas ：

/* 3  Minimum point coverage 、 The largest independent set 、 Minimum path point coverage ( Minimum path repeat point coverage )  The maximum number of matches  =  Minimum point coverage  =  Total points  -  The largest independent set  =  Total points  -  Minimum path coverage   matching / Match side :  An edge that has no common nodes with other edges ,  We call this edge a match / Match side .  Match points :  Match points on edges   Mismatches :  Points not on the matching edge   Unmatched edges :  The edge between two points in the graph is not the edge of the matching edge   The biggest match ( The maximum number of matching edges ):  How many edges are connected at most ,  So that all edges have no common points   Zengguang road ( path ):  The path from the unmatched point on one side to the unmatched point on the other side, where a unmatched edge and a matched edge pass alternately .  popular : Start with an unmatched vertex , After several matching vertices , Finally, the path to an unmatched vertex in the opposite set , That is, this path connects two unmatched vertices of two different sets through a series of matching vertices .  initial : The matching edge is a line (-), The unmatched edge is two lines (--) 1 o - o 2 \/ /\ 3 o o 4  here 3->2->1->4 It's just one.   Points on unmatched edges 3-> Points on unmatched edges 4 The path of expansion   This augmented path allows 3-2 matching ,1-4 Matching to achieve maximum matching  ( As long as there is one augmented path, there can be more than one set of matches ,  The biggest match  <=>  There is no augmentation path )  The minimum point covering problem   Definition :  Give us a picture ,  Choose the least of them ,  So that at least one vertex of each edge in the graph is selected   Three matching edges  = 1(\),2(\),3(-) o o \1 o .  Choose the least points ( Marked as ".")  So that at least one of the two points of each edge is selected  / / o o \2 o . . ——3o \ \ o  In a bipartite graph   Minimum point coverage == The maximum number of matches   Prove A = B  You need to prove that the minimum point covers A ≥  The maximum number of matches B -  The biggest match m- At least choose m A point to cover m One side ( There is no intersection in the match )  The maximum number of matches B =  Minimum point coverage A The equal sign can hold  -  Construct a scheme  -- Because the minimum point coverage is the minimum of all schemes   structure : 1  Maximum matching ( In Hungary, ) 2  Every unmatched point from the left {a,b} set out   Do an enlargement to the right ( Two dashed horizontal lines - -) o o \ ao - -. / / o o \ bo - -. . —— o \ \ o 3  Mark all passing points   Marked as .  And the point that has not been passed is still o . o \ -> e1 a.- -.3 / / . o \ -> e2 b.- -.2 1. —— o -> e3 \ \ oc  All unmarked points on the left {1} And all marked points on the right {2,3} 1  All non matching points on the left must be marked ( They are the starting point ) /  The unmarked point on the left must be a match point (1) 2  All non matching points on the right must not be marked ( Otherwise, you will find Zengguang road ) /  All marked points on the right must be matching points (2,3)  Review the definition of Zengguang road : From the left non matching point -> The path of the unmatched point on the right   The marked represents starting from the non matching point on the left to the non matching point on the right  3  For matching edges   The left and right points are either marked at the same time   Or not marked at the same time ( Because in the process of finding Zengguang road , The left matching point can only be reached through the right .)  For each matching edge, only one point must be selected  -  Select the marked point on the right {2,3}/ Choose the unmarked point on the left {1}  here : The point we chose (.) The number of == Number of matches (e1、e2、e3) 0  First, define the current satisfaction Hypothesis : The matching edges on the left and right must be covered by the matching edges in the largest matching tree   Whether the edge of the point not in the matching is covered by the matching edge in the maximum matching number ？ 1  Left unmatched point i →  Right matching point j ( As edge a-3, edge b-2)  because i It's the starting point , therefore j Must be marked . And we chose all the marked points on the right ( It's about ), So such edges are also covered . 2  The matching point on the left i →  Right mismatches j( As edge 1-c  Right mismatches == Unmarked points ) i It must not be marked , Otherwise, go to j We found Zengguang road . And we chose all the unmarked points on the left ( It's about ), So such edges are also covered .  Draw i The marked example shows why  0.-- . -> The marked points can be non matching points from the left 0 Set out and pass by i Before marking i Of  /  If you can get from i->j, It means that you find a 0-j It's an extension of the road , You can have one more matching edge  /  Conflict with the biggest match  i.—— o \ \ o j 3  The left and right don't match ( At this point, you can add a new edge to the maximum matching ) --  This is the biggest contradiction with the current matching   therefore   The case we constructed is just 3 Points and will be maximum 3 A matching edge covers  */

Code ：

/*  This topic  a[i]=0 || b[i]=0 You can skip   A task i Can be A、B Two states of the machine a[i]、b[i] complete , Think of a task as an edge , The two states are viewed as two endpoints ,  To complete a task, you need to choose one of these two points ( Tasks can be A Can also be executed on B On the implementation ),  For all tasks, start from N+M-2 Of points ( Does not include initial 0 state ) Choose the least points , Cover all edges ( Mission ),  The problem becomes the minimum point covering problem ( The minimum vertex covering in a bipartite graph is equivalent to the maximum matching number -- hungarian algorithm ). */


#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);
            //  Current i There must be no object 
            if (find(i))
                res++;
        }
        cout << res << endl;
    }

    return 0;
}