Pagini recente » Cod sursa (job #371825) | Cod sursa (job #1946699) | Cod sursa (job #3133375) | Cod sursa (job #2053011) | Cod sursa (job #3183442)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int bfs(int s, int t, vector<int>& tata, vector<vector<int>>& muchii,
vector<vector<int>>& cap, vector<vector<int>>& flux){
for(int i = 0; i < tata.size(); i++)
tata[i] = -1;
int f = INT_MAX;
tata[s] = s;
queue<int> q;
q.push(s);
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = 0; i < muchii[x].size(); i++){
int vecin = muchii[x][i];
if(tata[vecin] == -1 && flux[x][vecin] < cap[x][vecin]){
tata[vecin] = x;
if(f > cap[x][vecin] - flux[x][vecin])
f = cap[x][vecin] - flux[x][vecin];
if(t == vecin)
return f;
q.push(vecin);
}
}
}
return 0;
}
int main(){
ifstream f("harta.in");
ofstream g("harta.out");
int n;
f >> n;
int s = 0, t = 2*n+1;
vector<int> tata(t+1, -1);
vector<vector<int>> muchii(t+1);
vector<vector<int>> flux(t+1, vector<int>(t+1, 0));
vector<vector<int>> capacitate(t+1, vector<int>(t+1, 0));
for(int i = 1; i <= n; i++){
int x, y;
f >> x >> y;
muchii[i].push_back(s);
muchii[s].push_back(i);
capacitate[s][i] = x;
for(int j = 1; j <= n; j++)
if(i != j){
muchii[i].push_back(j+n);
muchii[j+n].push_back(i);
capacitate[i][j+n] = 1;
}
muchii[i+n].push_back(t);
muchii[t].push_back(i+n);
capacitate[i+n][t] = y;
}
int nrMuchii = 0;
while(1){
int f = bfs(s, t, tata, muchii, capacitate, flux);
if(f){
nrMuchii += f;
int x = t;
while(x != s){
int y = tata[x];
flux[y][x] += f;
flux[x][y] -= f;
x = y;
}
}
else
break;
}
g << nrMuchii << '\n';
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(flux[i][j+n])
g << i << ' ' << j << '\n';
return 0;
}