Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("O3")
- #pragma GCC target("avx2")
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <bitset>
- #include <set>
- #include <map>
- #include <string>
- #include <cmath>
- #include <queue>
- #include <ctime>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
- const ll SIZE= 1e5 * 3 + 10, INF = 1e9 * 1e9 + 2, MOD = 1e9 + 7;
- vector<vector<ll>> graph;
- ll q;
- vector<ll> vec;
- bool used[SIZE];
- struct edge {
- int c, bal, ind, to, fr = -1;
- };
- vector<edge> edges;
- int n, m, nd;
- int dfs(int v, int curMin = INT32_MAX) {
- used[v] = true;
- if (v == nd) {
- return curMin;
- }
- for (auto to : graph[v]) {
- if (edges[to].bal > 0 && !used[edges[to].to]) {
- int val = dfs(edges[to].to, min(curMin, edges[to].bal));
- if (val > 0) {
- curMin = min(val, curMin);
- edges[to].bal -= curMin;
- edges[to ^ 1].bal += curMin;
- return curMin;
- }
- }
- }
- return 0;
- }
- int main() {
- cin >> n >> m;
- nd = n + m + 1;
- graph.resize(n + m + 2);
- for (int i = 1; i <= n; i++) {
- int q;
- cin >> q;
- while (q != 0) {
- q += n;
- edges.push_back({ 1, 1, int(edges.size() - 1), q , i});
- edges.push_back({ 0, 0, int(edges.size() - 1), i});
- graph[i].push_back(edges.size() - 2);
- graph[q].push_back(edges.size() - 1);
- cin >> q;
- }
- }
- for (int i = 1; i <= n; i++) {
- edges.push_back({ 1, 1, int(edges.size() - 1), i });
- edges.push_back({ 0, 0, int(edges.size() - 1), 0 });
- graph[0].push_back(edges.size() - 2);
- graph[i].push_back(edges.size() - 1);
- }
- for (int i = n + 1; i <= n + m; i++) {
- edges.push_back({ 1, 1, int(edges.size() - 1), nd });
- edges.push_back({ 0, 0, int(edges.size() - 1), i });
- graph[i].push_back(edges.size() - 2);
- graph[nd].push_back(edges.size() - 1);
- }
- ll q = dfs(0);
- while (q != 0) {
- for (int i = 0; i <= nd; i++) used[i] = false;
- q = dfs(0);
- }
- vector<pair<ll, ll>> ans;
- for (int i = 0; i < edges.size(); i++) {
- if (edges[i].fr != -1 && edges[i].bal == 0) ans.push_back({ edges[i].fr, edges[i].to - n });
- }
- cout << ans.size() << "\n";
- for (int i = 0; i < ans.size(); i++) {
- cout << ans[i].first << " " << ans[i].second << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement