Pagini recente » Cod sursa (job #526917) | Cod sursa (job #2557552) | Cod sursa (job #2386777) | Cod sursa (job #3215294) | Cod sursa (job #2579629)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int INF = 0x3f3f3f3f;
int n;
int flo[214][214], cap[214][214];
vector<int> gra[214];
int edg = 0;
void nuke(){
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j){
cap[i][j+n] = 1;
}
}
}
for(int i = 1; i <= n; ++i){
gra[0].push_back(i);
gra[i].push_back(0);
gra[2*n+1].push_back(i+n);
gra[i+n].push_back(2*n+1);
}
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(i != j){
gra[i].push_back(j+n);
gra[j+n].push_back(i);
}
}
}
}
void read(){
fin >> n;
nuke();
for(int i = 1; i <= n; ++i){
int pin, pout;
fin >> pout >> pin;
cap[0][i] = pin;
cap[i+n][2*n+1] = pout;
edg += pin;
}
}
queue<int> qu;
bitset<214> vi;
int dad[214];
bool bfs(){
vi.reset();
qu.push(0);
vi[0] = true;
while(!qu.empty()){
int a = qu.front();
qu.pop();
if(a == 2*n+1)continue;
for(auto b : gra[a]){
if(vi[b] || flo[a][b] == cap[a][b])continue;
vi[b] = true;
if(b != 2*n+1)qu.push(b);
dad[b] = a;
}
}
return vi[2*n+1];
}
void solve(){
while(bfs()){
for(auto a : gra[2*n+1]){
if(!vi[a] || flo[a][2*n+1] == cap[a][2*n+1])continue;
int fmin = INF;
dad[2*n+1] = a;
for(int x = 2*n+1; x > 0; x = dad[x]){
fmin = min(fmin, cap[dad[x]][x] - flo[dad[x]][x]);
}
if(fmin == 0)continue;
for(int x = 2*n+1; x > 0; x = dad[x]){
flo[dad[x]][x] += fmin;
flo[x][dad[x]] -= fmin;
}
}
}
}
void write(){
fout << edg << "\n";
for(int i = 1; i <= n; ++i){
for(int j = 1; j <= n; ++j){
if(flo[i][j+n] == 1){
fout << i << " " << j << "\n";
}
}
}
}
int main(){
read();
solve();
write();
return 0;
}