Pagini recente » Cod sursa (job #927493) | Cod sursa (job #999410) | Cod sursa (job #2658039) | Cod sursa (job #809587) | Cod sursa (job #3264602)
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
void start() {
freopen("harta.in", "r", stdin); freopen("harta.out", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
cout << setprecision(12) << fixed;
srand(time(nullptr));
}
pair<int, vector<vector<int>>> compute_max_flow(int n_nodes, int source, int destination, vector<vector<int>> &cap){
assert(cap.size() == n_nodes+1);
for (int i=1; i<=n_nodes; i++){
assert(cap[i].size() == n_nodes+1);
}
vector<vector<int>> gr(n_nodes+1);
vector<vector<int>> flow(n_nodes+1, vector<int>(n_nodes+1, 0));
vector<int> dad(n_nodes+1, 0);
queue<int> q;
// make gr
for (int i=1; i<=n_nodes; i++){
for (int j=1; j<=n_nodes; j++){
if (cap[i][j]){
gr[i].push_back(j);
gr[j].push_back(i);
}
}
}
// Edmonds Karp
int ans = 0;
bool is_flow = true;
while (is_flow) {
// bfs
is_flow = false;
for (int i = 1; i <= n_nodes; i++) {
dad[i] = 0;
}
dad[source] = source;
q.push(source);
while (!q.empty()) {
int now = q.front();
q.pop();
if (now == destination) {
is_flow = true;
continue;
}
for (auto& x : gr[now]) {
if (!dad[x] && cap[now][x] - flow[now][x] > 0) {
dad[x] = now;
q.push(x);
}
}
}
// apply flow
for (auto& x : gr[destination]) {
if (!dad[x]) {
continue;
}
dad[destination] = x;
int now = destination;
int MIN = INT_MAX;
while (now != source) {
MIN = min(MIN, cap[dad[now]][now] - flow[dad[now]][now]);
now = dad[now];
}
now = destination;
while (now != source) {
flow[dad[now]][now] += MIN;
flow[now][dad[now]] -= MIN;
now = dad[now];
}
ans += MIN;
}
}
return {ans, flow};
}
int n;
vector<int> in, out;
void read() {
cin>>n;
in.resize(n+1);
out.resize(n+1);
for (int i=1; i<=n; i++){
cin>>out[i]>>in[i];
}
}
void solve() {
read();
int sum_in = 0, sum_out = 0;
for (int i=1; i<=n; i++){
sum_in += in[i];
sum_out += out[i];
}
if (sum_in != sum_out){
cout<<"NU"<<'\n';
return;
}
// MAKE GRAPH
int n_nodes = 1 + n + n + 1;
int source = 1;
int destination = n_nodes;
int offset_out = 1;
int offset_in = 1 + n;
vector<vector<int>> cap(n_nodes+1, vector<int>(n_nodes+1, 0));
// source to out
for (int i=1; i<=n; i++){
cap[source][i+offset_out] = out[i];
}
// out to in
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
if (i == j){
continue;
}
cap[i+offset_out][j+offset_in] = 1;
}
}
// in to destination
for (int i=1; i<=n; i++){
cap[i+offset_in][destination] = in[i];
}
auto result = compute_max_flow(n_nodes, source, destination, cap);
int max_flow = result.first;
vector<vector<int>> flow = result.second;
if (max_flow != sum_in){
cout<<"NU"<<'\n';
return;
}
cout<<max_flow<<'\n';
for (int i=1; i<=n; i++){
for (int j=1; j<=n; j++){
if (flow[i+offset_out][j+offset_in]){
cout<<i<<" "<<j<<'\n';
}
}
}
}
int main(){
start();
int t = 1;
// cin>>t;
for (int i=1; i<=t; i++){
solve();
}
return 0;
}