Pagini recente » Cod sursa (job #1923012) | Cod sursa (job #216088) | Cod sursa (job #1439875) | Cod sursa (job #2475440) | Cod sursa (job #2970657)
#include<bits/stdc++.h>
ifstream in("harta.in");
ofstream out("harta.out");
using namespace std;
int n, d1, d2,total;
int tata[202];
vector<vector<int>>lista;
int g[202][202];
int lab[202];
bool BFS() {
queue<int>q;
for(int i = 0; i <= 2 * n + 1; i++){
tata[i] = -1;
lab[i] = 0;
}
lab[0] = 1;
q.push(0);
while(!q.empty()){
int x = q.front();
q.pop();
for(auto el : lista[x]){
if(lab[el] == 0 && g[x][el] > 0){
tata[el] = x;
q.push(el);
lab[el] = 1;
if (el == 2*n+1){
return 1;
}
}
}
}
return 0;
}
int main(){
in >> n;
lista.resize(2*n + 2);
for(int i = 1; i <= n; i++){
in >> d1 >> d2;
g[0][i] = d1;
g[n+i][2*n + 1] = d2;
lista[0].push_back(i);
lista[i].push_back(0);
lista[n + i].push_back(2 * n + 1);
lista[2 * n + 1].push_back(n + i);
for(int j = n + 1; j <= 2 * n; j++){
if(j - i == n){
continue;
}
lista[i].push_back(j);
lista[j].push_back(i);
g[i][j] = 1;
}
}
while(BFS()){
for(auto element : lista[n]){
if (!lab[element]) {
continue;
}
int minim = 1e7 + 1;
int v = 2 * n + 1;
while(v != 0){
minim = min(minim, g[tata[v]][v]);
v = tata[v];
}
v = 2*n+1;
while(v != 0){
g[tata[v]][v] -= minim;
g[v][tata[v]] += minim;
v = tata[v];
}
total = total + minim;
}
}
out << total << "\n";
for(int i = 1; i <= n; i++){
for(int j = n + 1; j <= 2 * n + 1; j++){
if(g[j][i] == 1){
out << i <<' '<< j - n << '\n';
continue;
}
}
}
return 0;
}