|
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 |
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <map> #include <vector> using namespace std; //int gr[105][105]; vector<int> gr[105]; int n,m,k; int rside[105],lside[105]; bool visit[105]; bool dfs(int pos) { for(int i=0;i<gr[pos].size();i++) { if(visit[gr[pos][i]]) continue; visit[gr[pos][i]] = 1; if(lside[gr[pos][i]]==-1 || dfs(lside[gr[pos][i]])) { rside[pos] = gr[pos][i]; lside[gr[pos][i]]= pos; return 1; } } return 0; } int main() { int job,a,b; while(cin>>n)//row =machine A mode and colmn = machine B mode { if(n==0) break; cin>>m>>k; for(int i=0;i<105;i++) { gr[i].clear(); rside[i]=-1; lside[i]=-1; } for(int i=0;i<k;i++) { cin>>job>>a>>b; if(!a || !b) continue; gr[a].push_back(b); } int res = 0; for(int i=0;i<n;i++) { memset(visit,0,sizeof(visit)); if(dfs(i)) res+=1; } cout<<res<<"\n"; } return 0; } |