62 {
63 match_cps->clear();
64 u_size_ = association_mat.rows();
65 v_size_ = association_mat.cols();
66 if (u_size_ > v_size_) return false;
67 ex_u_ = new double[u_size_];
68 ex_v_ = new double[v_size_];
69 v_matched_ = new int[v_size_];
70 std::fill(v_matched_, v_matched_ + v_size_, -1);
71 memset(ex_v_, 0, v_size_ * sizeof(double));
72 for (int i = 0; i < u_size_; ++i) {
73 ex_u_[i] = association_mat(i, 0);
74 for (int j = 1; j < v_size_; ++j) {
75 ex_u_[i] = std::max(static_cast<float>(ex_u_[i]), association_mat(i, j));
76 }
77 }
78 for (int i = 0; i < u_size_; ++i) {
79 if (ex_u_[i] <= 0) {
80 if (need_reverse)
81 match_cps->push_back(std::make_pair(-1, i));
82 else
83 match_cps->push_back(std::make_pair(i, -1));
84 continue;
85 }
86 v_slack_ = new double[v_size_];
87 std::fill(v_slack_, v_slack_ + v_size_,
USR_INF);
88 while (1) {
89 used_u_.clear();
90 used_v_.clear();
91 if (FindCP(association_mat, i)) break;
93 for (int j = 0; j < v_size_; ++j)
94 if (used_v_.find(j) == used_v_.end()) d = std::min(d, v_slack_[j]);
95 for (auto it = used_u_.begin(); it != used_u_.end(); it++) {
96 ex_u_[*it] -= d;
97 }
98 for (int j = 0; j < v_size_; ++j) {
99 if (used_v_.find(j) != used_v_.end())
100 ex_v_[j] += d;
101 else
102 v_slack_[j] -= d;
103 }
104 }
105 delete[] v_slack_;
106 }
107 if (need_reverse) {
108 for (int j = 0; j < v_size_; ++j) {
109 if (v_matched_[j] == -1) {
110 match_cps->push_back(std::make_pair(j, -1));
111 } else if (association_mat(v_matched_[j], j) > 0) {
112 match_cps->push_back(std::make_pair(j, v_matched_[j]));
113 } else {
114 match_cps->push_back(std::make_pair(-1, v_matched_[j]));
115 match_cps->push_back(std::make_pair(j, -1));
116 }
117 }
118 } else {
119 for (int j = 0; j < v_size_; ++j) {
120 if (v_matched_[j] == -1) {
121 match_cps->push_back(std::make_pair(-1, j));
122 } else if (association_mat(v_matched_[j], j) > 0) {
123 match_cps->push_back(std::make_pair(v_matched_[j], j));
124 } else {
125 match_cps->push_back(std::make_pair(v_matched_[j], -1));
126 match_cps->push_back(std::make_pair(-1, j));
127 }
128 }
129 }
130 delete[] ex_u_;
131 delete[] ex_v_;
132 delete[] v_matched_;
133 return true;
134}