Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <list>
- #include <algorithm>
- using namespace std;
- bool kuhn(int v, vector<bool> &used, vector<int> &match, list<list<int>> G) {
- if (used[v]) return false;
- used[v] = true;
- list<list<int>>::iterator iter = G.begin();
- for (int i = 0; i < v; i++)
- iter++;
- list<int>::iterator u;
- for ( u = (*iter).begin();u != (*iter).end(); u++) {
- if (match[*u] == -1 || kuhn(match[*u], used,match,G)) {
- match[*u] = v;
- return true;
- }
- }
- return false;
- }
- int main() {
- ifstream in;
- in.open("matching.in");
- ofstream out;
- out.open("matching.out");
- int n;
- in >> n;
- vector<bool> used(n);
- vector<int> match(n,-1);
- list<list<int>> G(n);
- vector<pair<int,int>> vertex(n);
- for (int i = 0; i < n; i++) {
- int elem;
- in >> elem;
- vertex[i] = {i,elem};
- }
- std::sort(vertex.begin(), vertex.end(), [](std::pair<int,int> &left,
- std::pair<int,int> &right) {
- return left.second < right.second;
- });
- int cap;
- list<list<int>>::iterator iter;
- for ( iter = G.begin(); iter != G.end(); iter++){
- in >> cap;
- list<int>::iterator j;
- int k = 0;
- for (j = (*iter).begin(); k < cap; j++) {
- k++;
- int elem;
- in >> elem;
- (*j) = elem;
- cout << *j << " ";
- }
- cout << endl;
- }
- for(int i = 0; i < n; i++){
- //used.resize(n,false);
- for(int j = 0; j < used.size() ; j++) {
- used[j] = false;
- }
- kuhn(vertex[i].first,used,match,G);
- }
- vector<int> answer(n + 1);
- for (int i = 0; i < n; i++) {
- if(match[i] != -1){
- answer[match[i] + 1] = i + 1;
- }
- }
- for (int i = 1; i <= n ; i++) {
- cout << answer[i] << " ";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement