Pagini recente » Cod sursa (job #838679) | Cod sursa (job #558830) | Cod sursa (job #1419631) | Cod sursa (job #910180) | Cod sursa (job #3193528)
#include "bits/stdc++.h"
#include <type_traits>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")
// ============ Macros starts here ============
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif // DEBUG
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) {
os << "[";
for (auto& x : v) { os << x << ", "; }
return os << "]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
return os << "{" << p.first << ", " << p.second << "}";
}
#define readFast \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#ifdef LOCAL
#define read() ifstream fin("date.in.txt")
#else
#define read() readFast
#endif // LOCAL
// ============ Macros ends here ============
#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n")
#define LSB(x) (x & (-x))
#define test cout << "WORKS\n";
const int N = 2e5 + 15;
const int MOD = 1e9 + 7; // 998244353
int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;
const int INF = 1e9;
int bfs(int s, int t, vector<int>& parent) {
fill(parent.begin(), parent.end(), -1);
parent[s] = -2;
queue<pair<int, int>> q;
q.push({ s, INF });
while (!q.empty()) {
int cur = q.front().first;
int flow = q.front().second;
q.pop();
for (int next : adj[cur]) {
if (parent[next] == -1 && capacity[cur][next]) {
parent[next] = cur;
int new_flow = min(flow, capacity[cur][next]);
if (next == t)
return new_flow;
q.push({ next, new_flow });
}
}
}
return 0;
}
int maxflow(int s, int t) {
int flow = 0;
vector<int> parent(202);
int new_flow;
while (new_flow = bfs(s, t, parent)) {
flow += new_flow;
int cur = t;
while (cur != s) {
int prev = parent[cur];
capacity[prev][cur] -= new_flow;
capacity[cur][prev] += new_flow;
cur = prev;
}
}
return flow;
}
int main() {
// read();
ifstream fin("harta.in");
ofstream cout("harta.out");
fin >> n;
int s = 0, t = n + n + 1;
capacity.resize(202, vector<int>(202, 0));
adj.resize(202);
for (int i = 1; i <= n; ++i) {
int dgOut, dgIn;
fin >> dgOut >> dgIn;
adj[s].push_back(i);
capacity[s][i] = dgOut;
adj[n + i].push_back(t);
capacity[n + i][t] = dgIn;
for (int j = 1; j <= n; ++j) {
if (i == j)
continue;
adj[i].push_back(n + j);
capacity[i][n + j] = 1;
adj[n + j].push_back(i);
// capacity[n + j][i] = 1;
}
}
cout << maxflow(s, t) << '\n';
for (int i = 1; i <= n; ++i) {
for (int x : adj[i]) {
if (capacity[i][x] == 0) {
cout << i << " " << x - n << '\n';
}
}
}
return 0;
} /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* test the solution with the given example
* int overflow, array bounds, matrix bounds
* special cases (n=1?)
* do smth instead of nothing and stay organized
* WRITE STUFF DOWN
* DON'T GET STUCK ON ONE APPROACH
~Benq~*/
/*
int dsu_find(int nod) {
if (tata[nod] == nod) {
return nod;
}
return tata[nod] = dsu_find(tata[nod]);
}
bool dsu_union(int a, int b) {
a = dsu_find(a);
b = dsu_find(b);
if (a != b) {
if (height[a] < height[b])
swap(a,b);
tata[a] = b;
if (height[a] == height[b]) {
++height[a];
}
return true;
}
return false;
}
bool cmp(const vector<int>& a, const vector<int>& b) {
return a[2] < b[2];
}
*/