Pagini recente » Cod sursa (job #2553276) | Cod sursa (job #3144721) | Cod sursa (job #1184194) | Cod sursa (job #145236) | Cod sursa (job #3262752)
#include<bits/stdc++.h>
#define cin fin
#define cout fout
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int inf = 1e9;
struct MFDinitz{
struct Edge{
int u, w, cap, flow;
Edge(int _u, int _w, int _cap){
u = _u;
w = _w;
cap = _cap;
flow = 0;
}
};
vector<Edge> e;
vector<vector<int>>e2;
int n, source, sink;
MFDinitz(int _n, int _source, int _sink){
n = _n;
source = _source;
sink = _sink;
e2.resize(n);
}
void add_edge(int u, int w, int cap){
e2[u].push_back(e.size());
e.push_back(Edge(u, w, cap));
e2[w].push_back(e.size());
e.push_back(Edge(w, u, 0));
}
vector <int> dist;
vector <int> pt;
vector <int> path;
void graph_algorithm(){
dist = vector<int>(n, -1);
dist[source] = 0;
queue <int> q;
q.push(source);
while(!q.empty()){
int node = q.front();
q.pop();
for(auto edgeid : e2[node]){
Edge edge = e[edgeid];
if(edge.flow == edge.cap)continue;
if(dist[edge.w] == -1){
dist[edge.w] = dist[edge.u] + 1;
q.push(edge.w);
}
}
}
}
int dfs(int node){
if(node == sink){
return inf;
}
while(pt[node] < e2[node].size()){
int id = e2[node][pt[node]];
Edge edge = e[id];
if(edge.flow < edge.cap && dist[edge.w] == dist[edge.u] + 1){
int x = dfs(edge.w);
if(x > 0){
path.push_back(id);
return min(x, edge.cap - edge.flow);
}
}
pt[node]++;
}
}
int max_flow(){
int f = 0;
while(1){
graph_algorithm();
if(dist[sink] == -1)break;
pt = vector<int>(n, 0);
while(1){
path.clear();
int nr = dfs(source);
if(nr == 0)break;
for(auto i : path){
e[i].flow+=nr;
e[i^1].flow-=nr;
}
f+=nr;
}
}
return f;
}
};
int main(){
int n, a = 0, b = 0;
cin>>n;
MFDinitz flow(2*n + 2, 0, 2*n + 1);
for(int i = 0;i < n;i++){
int u, w;
cin>>u>>w;
a+=u;
b+=w;
flow.add_edge(0, i + 1, u);
flow.add_edge(i + 1 + n, 2*n + 1, w);
}
for(int i = 1;i <= n;i++){
for(int j = n + 1;j <= 2*n;j++){
if(i != j - n){
flow.add_edge(i, j, 1);
}
}
}
if(a == b && flow.max_flow() == a){
cout<<a<<'\n';
for(int i = 1;i <= n;i++){
for(auto j : flow.e2[i]){
auto edge = flow.e[j];
if(n + 1 <= edge.w && edge.w <= 2*n && edge.cap == edge.flow){
cout<<edge.u<<' '<<edge.w - n<<'\n';
}
}
}
}
return 0;
}