Pagini recente » Profil sjulean | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3361137) | Cod sursa (job #3361210)
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, m, maxflux;
pair <int, int> drum;
struct much{
int a, b, c, f;
};
vector <much> a;
vector <int> v[205];
int last[205];
queue <int> q;
void bfslave(){
for(int i = 0; i <= 2 * n + 1; i++){
last[i] = -1;
}
last[0] = -2;
q.push(0);
int nod;
much nxt;
while(!q.empty()){
nod = q.front();
q.pop();
for(int i = 0; i < v[nod].size(); i++){
nxt = a[v[nod][i]];
if(nxt.f < nxt.c && last[nxt.b] == -1){
last[nxt.b] = v[nod][i];
q.push(nxt.b);
}
}
}
}
void fa_un_drum(){
int nod = 2 * n + 1;
int minim_ude = INT_MAX;
while(last[nod] != -2){
minim_ude = min(minim_ude, a[last[nod]].c - a[last[nod]].f);
nod = a[last[nod]].a;
}
maxflux += minim_ude;
nod = 2 * n + 1;
while(last[nod] != -2){
a[last[nod]].f += minim_ude;
a[(last[nod]+m)%(2*m)].f -= minim_ude;
nod = a[last[nod]].a;
}
}
void fa_drumurile(){
int mettaton;
for(int i = 0; i < v[2*n+1].size(); i++){
mettaton = v[2*n+1][i];
if(last[a[mettaton].b] != -1){
last[2*n+1] = mettaton - m;
fa_un_drum();
}
}
}
void flux(){
int lastflux = -1;
while(lastflux != maxflux){
lastflux = maxflux;
bfslave();
fa_drumurile();
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
fin >> n;
for(int i = 1; i <= n; i++){
fin >> drum.f >> drum.s;
a.push_back({0, i, drum.f, 0});
a.push_back({i + n, 2 * n + 1, drum.s, 0});
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(i != j){
a.push_back({i, j + n, 1, 0});
}
}
}
m = a.size();
for(int i = 0; i < m; i++){
v[a[i].a].push_back(i);
a.push_back({a[i].b, a[i].a, 0, 0});
v[a[i].b].push_back(i + m);
}
flux();
fout << maxflux << "\n";
for(int i = 2 * n; i < m; i++){
if(a[i].f == a[i].c){
fout << a[i].a << " " << a[i].b - n << "\n";
}
}
return 0;
}