Pagini recente » Cod sursa (job #2161112) | Cod sursa (job #922756) | Cod sursa (job #1372322) | Cod sursa (job #1359416) | Cod sursa (job #2917123)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
const int N = 210, inf = 1e9;
int in[N + 1], out[N + 1];
int f[N + 1][N + 1], parent[N + 1], S, D, n;
bool viz[N + 1];
vector <int> adj[N + 1];
bool BFS(){
for(int i = 0; i <= 2 * n + 1; i++)
parent[i] = viz[i] = 0;
queue <int> Q;
Q.push(S);
viz[S] = true;
while(!Q.empty()){
int nod = Q.front();
Q.pop();
if(nod == D)
return true;
for(auto vec : adj[nod]){
if(!viz[vec] && f[nod][vec] > 0)
parent[vec] = nod, viz[vec] = true, Q.push(vec);
}
}
return false;
}
int main(){
fin >> n;
for(int i = 1; i <= n; i++)
fin >> out[i] >> in[i];
S = 0, D = 2 * n + 1;
for(int i = 1; i <= n; i++){
adj[S].push_back(i);
adj[i].push_back(S);
f[S][i] = out[i];
}
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n; j++){
if(j != i + n){
adj[i].push_back(j);
adj[j].push_back(i);
f[i][j] = 1;
}
}
for(int i = n + 1; i <= 2 * n; i++){
adj[i].push_back(D);
adj[D].push_back(i);
f[i][D] = in[i - n];
}
int maxFlow = 0;
while(BFS()){
for(auto vec : adj[D]){
if(f[vec][D] <= 0 || !viz[vec])
continue;
parent[D] = vec;
int mini = inf, nod = D;
while(nod != S)
mini = min(mini, f[parent[nod]][nod]), nod = parent[nod];
if(mini == 0)
continue;
nod = D;
while(nod != S)
f[parent[nod]][nod] -= mini, f[nod][parent[nod]] += mini, nod = parent[nod];
maxFlow += mini;
}
}
fout << maxFlow << '\n';
for(int i = 1; i <= n; i++)
for(int j = n + 1; j <= 2 * n; j++)
if(f[i][j] == 0 && f[j][i] != 0)
fout << i << ' ' << j - n << '\n';
return 0;
}