// C++ implementation of Hopcroft Karp algorithm for // maximum matching #include<bits/stdc++.h> using namespace std; #define NIL 0 #define INF INT_MAX // A class to represent Bipartite graph for Hopcroft // Karp implementation class BipGraph { // m and n are number of vertices on left // and right sides of Bipartite Graph int m, n; // adj[u] stores adjacents of left side // vertex 'u'. The value of u ranges from 1 to m. // 0 is used for dummy vertex list<int> *adj; // These are basically pointers to arrays needed // for hopcroftKarp() int *pairU, *pairV, *dist; public: BipGraph(int m, int n); // Constructor void addEdge(int u, int v); // To add edge // Returns true if there is an augmenting path bool bfs(); // Adds augmenting path if there is one beginning // with u bool dfs(int u); // Returns size of maximum matcing int hopcroftKarp(); }; // Returns size of maximum matching int BipGraph::hopcroftKarp() { // pairU[u] stores pair of u in matching where u // is a vertex on left side of Bipartite Graph. // If u doesn't have any pair, then pairU[u] is NIL pairU = new int[m+1]; // pairV[v] stores pair of v in matching. If v // doesn't have any pair, then pairU[v] is NIL pairV = new int[n+1]; // dist[u] stores distance of left side vertices // dist[u] is one more than dist[u'] if u is next // to u'in augmenting path dist = new int[m+1]; // Initialize NIL as pair of all vertices for (int u=0; u<=m; u++) pairU[u] = NIL; for (int v=0; v<=n; v++) pairV[v] = NIL; // Initialize result int result = 0; // Keep updating the result while there is an // augmenting path. while (bfs()) { // Find a free vertex for (int u=1; u<=m; u++) // If current vertex is free and there is // an augmenting path from current vertex if (pairU[u]==NIL && dfs(u)) result++; } return result; } // Returns true if there is an augmenting path, else returns // false bool BipGraph::bfs() { queue<int> Q; //an integer queue // First layer of vertices (set distance as 0) for (int u=1; u<=m; u++) { // If this is a free vertex, add it to queue if (pairU[u]==NIL) { // u is not matched dist[u] = 0; Q.push(u); } // Else set distance as infinite so that this vertex // is considered next time else dist[u] = INF; } // Initialize distance to NIL as infinite dist[NIL] = INF; // Q is going to contain vertices of left side only. while (!Q.empty()) { // Dequeue a vertex int u = Q.front(); Q.pop(); // If this node is not NIL and can provide a shorter path to NIL if (dist[u] < dist[NIL]) { // Get all adjacent vertices of the dequeued vertex u list<int>::iterator i; for (i=adj[u].begin(); i!=adj[u].end(); ++i) { int v = *i; // If pair of v is not considered so far // (v, pairV[V]) is not yet explored edge. if (dist[pairV[v]] == INF) { // Consider the pair and add it to queue dist[pairV[v]] = dist[u] + 1; Q.push(pairV[v]); } } } } // If we could come back to NIL using alternating path of distinct // vertices then there is an augmenting path return (dist[NIL] != INF); } // Returns true if there is an augmenting path beginning with free vertex u bool BipGraph::dfs(int u) { if (u != NIL) { list<int>::iterator i; for (i=adj[u].begin(); i!=adj[u].end(); ++i) { // Adjacent to u int v = *i; // Follow the distances set by BFS if (dist[pairV[v]] == dist[u]+1) { // If dfs for pair of v also returns // true if (dfs(pairV[v]) == true) { pairV[v] = u; pairU[u] = v; return true; } } } // If there is no augmenting path beginning with u. dist[u] = INF; return false; } return true; } // Constructor BipGraph::BipGraph(int m, int n) { this->m = m; this->n = n; adj = new list<int>[m+1]; } // To add edge from u to v and v to u void BipGraph::addEdge(int u, int v) { adj[u].push_back(v); // Add u to v’s list. } struct Pair { int w, t; }; bool comp(const Pair t1, const Pair t2) { return t1.w-t1.t < t2.w-t2.t; } int main() { ios::sync_with_stdio(0); //freopen("sam00.in", "r", stdin); int n; cin >> n; vector<Pair> v1, v2; for(int i=0; i<n; ++i) { int r, w, t; cin >> r >> w >> t; if(r==1) v1.push_back(Pair{w,t}); else v2.push_back(Pair{w,t}); } sort(v1.begin(), v1.end(), comp); sort(v2.begin(), v2.end(), comp); BipGraph g(v1.size(), v2.size()); for(int i=0; i<v1.size(); ++i) { //cout << v1[i].w << " " << v1[i].t << endl; auto it1 = lower_bound(v2.begin(), v2.end(), Pair{v1[i].w, v1[i].t}, comp); auto it2 = upper_bound(v2.begin(), v2.end(), Pair{v1[i].w, v1[i].t}, comp); for(auto it = it1; it!=it2; ++it) { //cout << "*** " << it->w << " " << it->t << endl; g.addEdge(i+1, it-v2.begin()+1); } } cout << g.hopcroftKarp() << endl; }
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 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 | // C++ implementation of Hopcroft Karp algorithm for // maximum matching #include<bits/stdc++.h> using namespace std; #define NIL 0 #define INF INT_MAX // A class to represent Bipartite graph for Hopcroft // Karp implementation class BipGraph { // m and n are number of vertices on left // and right sides of Bipartite Graph int m, n; // adj[u] stores adjacents of left side // vertex 'u'. The value of u ranges from 1 to m. // 0 is used for dummy vertex list<int> *adj; // These are basically pointers to arrays needed // for hopcroftKarp() int *pairU, *pairV, *dist; public: BipGraph(int m, int n); // Constructor void addEdge(int u, int v); // To add edge // Returns true if there is an augmenting path bool bfs(); // Adds augmenting path if there is one beginning // with u bool dfs(int u); // Returns size of maximum matcing int hopcroftKarp(); }; // Returns size of maximum matching int BipGraph::hopcroftKarp() { // pairU[u] stores pair of u in matching where u // is a vertex on left side of Bipartite Graph. // If u doesn't have any pair, then pairU[u] is NIL pairU = new int[m+1]; // pairV[v] stores pair of v in matching. If v // doesn't have any pair, then pairU[v] is NIL pairV = new int[n+1]; // dist[u] stores distance of left side vertices // dist[u] is one more than dist[u'] if u is next // to u'in augmenting path dist = new int[m+1]; // Initialize NIL as pair of all vertices for (int u=0; u<=m; u++) pairU[u] = NIL; for (int v=0; v<=n; v++) pairV[v] = NIL; // Initialize result int result = 0; // Keep updating the result while there is an // augmenting path. while (bfs()) { // Find a free vertex for (int u=1; u<=m; u++) // If current vertex is free and there is // an augmenting path from current vertex if (pairU[u]==NIL && dfs(u)) result++; } return result; } // Returns true if there is an augmenting path, else returns // false bool BipGraph::bfs() { queue<int> Q; //an integer queue // First layer of vertices (set distance as 0) for (int u=1; u<=m; u++) { // If this is a free vertex, add it to queue if (pairU[u]==NIL) { // u is not matched dist[u] = 0; Q.push(u); } // Else set distance as infinite so that this vertex // is considered next time else dist[u] = INF; } // Initialize distance to NIL as infinite dist[NIL] = INF; // Q is going to contain vertices of left side only. while (!Q.empty()) { // Dequeue a vertex int u = Q.front(); Q.pop(); // If this node is not NIL and can provide a shorter path to NIL if (dist[u] < dist[NIL]) { // Get all adjacent vertices of the dequeued vertex u list<int>::iterator i; for (i=adj[u].begin(); i!=adj[u].end(); ++i) { int v = *i; // If pair of v is not considered so far // (v, pairV[V]) is not yet explored edge. if (dist[pairV[v]] == INF) { // Consider the pair and add it to queue dist[pairV[v]] = dist[u] + 1; Q.push(pairV[v]); } } } } // If we could come back to NIL using alternating path of distinct // vertices then there is an augmenting path return (dist[NIL] != INF); } // Returns true if there is an augmenting path beginning with free vertex u bool BipGraph::dfs(int u) { if (u != NIL) { list<int>::iterator i; for (i=adj[u].begin(); i!=adj[u].end(); ++i) { // Adjacent to u int v = *i; // Follow the distances set by BFS if (dist[pairV[v]] == dist[u]+1) { // If dfs for pair of v also returns // true if (dfs(pairV[v]) == true) { pairV[v] = u; pairU[u] = v; return true; } } } // If there is no augmenting path beginning with u. dist[u] = INF; return false; } return true; } // Constructor BipGraph::BipGraph(int m, int n) { this->m = m; this->n = n; adj = new list<int>[m+1]; } // To add edge from u to v and v to u void BipGraph::addEdge(int u, int v) { adj[u].push_back(v); // Add u to v’s list. } struct Pair { int w, t; }; bool comp(const Pair t1, const Pair t2) { return t1.w-t1.t < t2.w-t2.t; } int main() { ios::sync_with_stdio(0); //freopen("sam00.in", "r", stdin); int n; cin >> n; vector<Pair> v1, v2; for(int i=0; i<n; ++i) { int r, w, t; cin >> r >> w >> t; if(r==1) v1.push_back(Pair{w,t}); else v2.push_back(Pair{w,t}); } sort(v1.begin(), v1.end(), comp); sort(v2.begin(), v2.end(), comp); BipGraph g(v1.size(), v2.size()); for(int i=0; i<v1.size(); ++i) { //cout << v1[i].w << " " << v1[i].t << endl; auto it1 = lower_bound(v2.begin(), v2.end(), Pair{v1[i].w, v1[i].t}, comp); auto it2 = upper_bound(v2.begin(), v2.end(), Pair{v1[i].w, v1[i].t}, comp); for(auto it = it1; it!=it2; ++it) { //cout << "*** " << it->w << " " << it->t << endl; g.addEdge(i+1, it-v2.begin()+1); } } cout << g.hopcroftKarp() << endl; } |