Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- typedef vector<vector<int>> matrix;
- bool check(const matrix m) {
- // проверим матрицу
- if (m.size() == 0 || m[0].size() == 0) return false;
- // первый проход
- for (int i = 0; i < m.size(); i++) {
- int count = 0;
- for (int j = 0; j < m[i].size(); j++) {
- if (m[i][j] == 0) count++;
- }
- if (count != 1) return false;
- }
- for (int i = 0; i < m[0].size(); i++) {
- int count = 0;
- for (int j = 0; j < m.size(); j++) {
- if (m[j][i] == 0) count++;
- }
- if (count != 1) return false;
- }
- return true;
- }
- int main() {
- matrix p1 = { {0,4,2,2},{6,0,0,4},{0,0,6,4},{8,4,0,0}};
- matrix p2 = { {0,6,4,4},{4,0,3,4},{0,2,8,6},{6,4,5,0}};
- matrix p3 = { {0,6,4,4},{4,3,0,4},{1,0,8,6},{6,4,6,0}};
- cout << "p1 = " << check(p1) << endl;
- cout << "p2 = " << check(p2) << endl;
- cout << "p3 = " << check(p3) << endl;
- return 0;
- }
- #include <vector>
- #include <iostream>
- #include <iomanip>
- using namespace std;
- vector<vector<int>> p1 = { {0,4,2,2},{6,0,0,4},{0,0,6,4},{8,4,0,0}};
- vector<vector<int>> p2 = { {0,6,4,4},{4,0,0,4},{0,2,8,6},{6,4,0,0}};
- vector<vector<int>> bipartee(const vector<vector<int>>& q)
- {
- vector<vector<int>> p;
- for(size_t r = 0; r < q.size(); ++r)
- {
- p.push_back(vector<int>());
- for(size_t c = 0; c < q.size(); ++c)
- if (q[r][c] == 0) p[r].push_back(c);
- }
- return p;
- }
- bool try_kuhn(int v, vector<vector<int>>& g, vector<int>& mt, vector<bool>& used)
- {
- if (used[v]) return false;
- used[v] = true;
- for (size_t i=0; i<g[v].size(); ++i) {
- int to = g[v][i];
- if (mt[to] == -1 || try_kuhn(mt[to],g,mt,used))
- {
- mt[to] = v;
- return true;
- }
- }
- return false;
- }
- bool check(const vector<vector<int>>& p)
- {
- int n = p.size();
- vector<vector<int>> g = bipartee(p);
- vector<int> mt;
- vector<bool> used;
- mt.assign(n, -1);
- for(int v = 0; v < n; ++v) {
- used.assign(n,false);
- try_kuhn(v,g,mt,used);
- }
- int sum = 0;
- for (int i=0; i<n; ++i)
- if (mt[i] != -1) ++sum;
- return (sum == n);
- }
- int main()
- {
- cout << "First matrix: " << check(p1) << endl;
- cout << "Second matrix: " << check(p2) << endl;
- }
- vector<vector<int>> p1 = { {0, 4, 2, 2}, {6, 0, 0, 4}, {0, 0, 6, 4}, {8, 4, 0, 0}};
- vector<vector<int>> p2 = { {0, 6, 4, 4}, {4, 0, 0, 4}, {0, 2, 8, 6}, {6, 4, 0, 0}};
- bool check(const vector<vector<int>>& p, int r = 0)
- {
- int n = p.size();
- static vector<bool> u;
- if (r == n) return true;
- if (r == 0) u = vector<bool>(n,false);
- for(int c = 0; c < n; ++c)
- {
- if (p[r][c] || u[c]) continue;
- u[c] = true;
- if (check(p,r+1)) return true;
- u[c] = false;
- }
- return false;
- }
- int main()
- {
- cout << "First matrix: " << check(p1) << endl;
- cout << "Second matrix: " << check(p2) << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement