#include <bits/stdc++.h> using namespace std; int n, M, N, m, q, a, b, c, d; vector<set<int> > vec; bool bpm(int u, bool seen[], int matchR[]) { for (int v = 0; v < N; v++) { if (vec[u].find(v)!=vec[u].end() && !seen[v]) { seen[v] = true; if (matchR[v] < 0 || bpm(matchR[v], seen, matchR)) { matchR[v] = u; return true; } } } return false; } int maxBPM() { int matchR[N]; memset(matchR, -1, sizeof(matchR)); int result = 0; for (int u = 0; u < M; u++) { bool seen[N]; memset(seen, 0, sizeof(seen)); if (bpm(u, seen, matchR)) result++; } return result; } int main() { cin>>n>>m>>q; bool tab[n][n]; N=n*n; M=N; for(int u=0;u<n;u++) for(int i=0;i<n;i++) { vec.push_back({}); tab[u][i]=0; } for(int i=0;i<m;i++) { cin>>a>>b>>c>>d; for(int u=a-1;u<c;u++) { for(int j=b-1;j<d;j++) { tab[u][j]^=1; } } } for(int i=0;i<n;i++) { for(int u=0;u<n;u++) { if(tab[i][u]) { for(int j=0;j<n;j++) if(!tab[i][j]) vec[i*n+u].insert(i*n+j); for(int j=0;j<n;j++) if(!tab[j][u]) vec[i*n+u].insert(j*n+u); } } } cout <<maxBPM()<<endl; for(int i=0;i<q;i++) { cin>>a>>b; a--; b--; tab[a][b]^=1; if(tab[a][b]) { for(int j=0;j<n;j++) { if(!tab[a][j]) vec[a*n+b].insert(a*n+j); else if(vec[a*n+j].find(a*n+b)!=vec[a*n+j].end()) { vec[a*n+j].erase(vec[a*n+j].find(a*n+b)); } //else cout<<a<<' '<<b<<' '<<j<<endl; } for(int j=0;j<n;j++) { if(!tab[j][b]) vec[a*n+b].insert(j*n+b); else if(vec[j*n+b].find(a*n+b)!=vec[j*n+b].end()) vec[j*n+b].erase(vec[j*n+b].find(a*n+b)); //else cout<<a<<' '<<b<<' '<<j<<endl; } } else { vec[a*n+b].clear(); for(int j=0;j<n;j++) if(tab[a][j]) vec[a*n+j].insert(a*n+b); for(int j=0;j<n;j++) if(tab[j][b]) vec[j*n+b].insert(a*n+b); } cout <<maxBPM()<<endl; } 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 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 | #include <bits/stdc++.h> using namespace std; int n, M, N, m, q, a, b, c, d; vector<set<int> > vec; bool bpm(int u, bool seen[], int matchR[]) { for (int v = 0; v < N; v++) { if (vec[u].find(v)!=vec[u].end() && !seen[v]) { seen[v] = true; if (matchR[v] < 0 || bpm(matchR[v], seen, matchR)) { matchR[v] = u; return true; } } } return false; } int maxBPM() { int matchR[N]; memset(matchR, -1, sizeof(matchR)); int result = 0; for (int u = 0; u < M; u++) { bool seen[N]; memset(seen, 0, sizeof(seen)); if (bpm(u, seen, matchR)) result++; } return result; } int main() { cin>>n>>m>>q; bool tab[n][n]; N=n*n; M=N; for(int u=0;u<n;u++) for(int i=0;i<n;i++) { vec.push_back({}); tab[u][i]=0; } for(int i=0;i<m;i++) { cin>>a>>b>>c>>d; for(int u=a-1;u<c;u++) { for(int j=b-1;j<d;j++) { tab[u][j]^=1; } } } for(int i=0;i<n;i++) { for(int u=0;u<n;u++) { if(tab[i][u]) { for(int j=0;j<n;j++) if(!tab[i][j]) vec[i*n+u].insert(i*n+j); for(int j=0;j<n;j++) if(!tab[j][u]) vec[i*n+u].insert(j*n+u); } } } cout <<maxBPM()<<endl; for(int i=0;i<q;i++) { cin>>a>>b; a--; b--; tab[a][b]^=1; if(tab[a][b]) { for(int j=0;j<n;j++) { if(!tab[a][j]) vec[a*n+b].insert(a*n+j); else if(vec[a*n+j].find(a*n+b)!=vec[a*n+j].end()) { vec[a*n+j].erase(vec[a*n+j].find(a*n+b)); } //else cout<<a<<' '<<b<<' '<<j<<endl; } for(int j=0;j<n;j++) { if(!tab[j][b]) vec[a*n+b].insert(j*n+b); else if(vec[j*n+b].find(a*n+b)!=vec[j*n+b].end()) vec[j*n+b].erase(vec[j*n+b].find(a*n+b)); //else cout<<a<<' '<<b<<' '<<j<<endl; } } else { vec[a*n+b].clear(); for(int j=0;j<n;j++) if(tab[a][j]) vec[a*n+j].insert(a*n+b); for(int j=0;j<n;j++) if(tab[j][b]) vec[j*n+b].insert(a*n+b); } cout <<maxBPM()<<endl; } return 0; } |