Pagini recente » Cod sursa (job #2856905) | Cod sursa (job #2527551) | Cod sursa (job #978177) | Cod sursa (job #1023260) | Cod sursa (job #2957164)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define cin f
#define cout g
// #define int long long
const int Max = 1e5 + 1;
void nos()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
#define pb push_back
const int INF = 1e9;
struct Edge {
int x;
int flow;
int cap;
int nxt;
};
struct Dinic {
int source;
int sink;
int n;
vector <vector <Edge>> gr;
vector <int> dist;
vector <int> start;
Dinic (int _source, int _sink, int _size) {
source = _source;
sink = _sink;
n = _size;
gr.resize (_size + 1);
dist.resize (_size + 1);
start.resize (_size + 1);
}
void add_edge (int x, int y, int cap) {
gr[x].pb ({y, 0, cap, gr[y].size ()});
gr[y].pb ({x, 0, 0, gr[x].size () - 1});
}
bool bfs () {
for (int i = 1; i <= n; i++)
dist[i] = -1;
dist[source] = 0;
queue <int> q;
q.push (source);
while (q.size ()) {
int node = q.front ();
q.pop ();
for (auto vec : gr[node]) {
if (dist[vec.x] == - 1 && vec.cap > vec.flow) {
dist[vec.x] = dist[node] + 1;
q.push (vec.x);
}
}
}
return dist[sink] != -1;
}
int dfs (int node, int sink, int flow) {
if (node == sink)
return flow;
while (start[node] < gr[node].size ()) {
Edge e = gr[node][start[node]];
if (dist[e.x] == dist[node] + 1 && e.flow < e.cap) {
int new_flow = dfs (e.x, sink, min (flow, e.cap - e.flow));
if (new_flow > 0) {
gr[node][start[node]].flow += new_flow;
gr[e.x][e.nxt].flow -= new_flow;
return new_flow;
}
}
start[node]++;
}
return 0;
}
int maxflow () {
int ans = 0;
while (bfs ()) {
int flow;
for (auto &x : start) x = 0;
while (flow = dfs (source, sink, INF))
ans += flow;
}
return ans;
}
};
int n;
int out[Max],in[Max];
void read()
{
f >> n;
int i;
for(i = 1;i <= n;i++)
f >> out[i] >> in[i];
}
void solve()
{
Dinic flow(0,2*n + 1, 2*n+1);
int i,j;
for(int i=1;i<=n;i++)
{
flow.add_edge(0,i,out[i]);
for(int j=1;j<=n;j++)
if(i != j)
flow.add_edge(i,j+n,1);
flow.add_edge(i+n,2*n + 1,in[i]);
}
cout << flow.maxflow() << '\n';
vector < pair < int , int > > ans;
for(int i=1;i<=n;i++)
for(auto it : flow.gr[i])
if(it.x != 0 and it.flow)
ans.push_back({i,it.x - n});
for(auto it : ans)
cout<<it.first<<' '<<it.second<<'\n';
}
void restart()
{
}
int32_t main()
{
nos();
// int teste;
// f>>teste;
// while(teste--)
{
read();
solve();
restart();
}
return 0;
}