Pagini recente » Cod sursa (job #192604) | Cod sursa (job #3148373) | Cod sursa (job #1591030) | Cod sursa (job #1143954) | Cod sursa (job #1498388)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
template <typename T>
using mat = vector<vector<T> >;
int flux_max(const int surs, const int dest,
const mat<int>& adiac, const mat<int>& cap, mat<int>& flux){
const int n = adiac.size();
vector<int> tata(n, 0);
queue<int> de_viz;
int rez = 0;
while(true){
fill(begin(tata), end(tata), -1);
tata[surs] = surs;
de_viz.push(surs);
while(!de_viz.empty()){
const int cur = de_viz.front();
de_viz.pop();
for(const auto next : adiac[cur]){
if(tata[next] == -1 && cap[cur][next] - flux[cur][next] > 0){
tata[next] = cur;
de_viz.push(next); } } }
if(tata[dest] == -1){
return rez; }
for(const auto last : adiac[dest]){
if(tata[last] != -1 && cap[last][dest] - flux[last][dest] > 0)
tata[dest] = last;
int f_min = 1000000000;
for(int nod = dest; nod != surs && f_min > 0; nod = tata[nod]){
f_min = min(f_min,
cap[tata[nod]][nod] - flux[tata[nod]][nod]); }
if(f_min > 0){
for(int nod = dest; nod != surs; nod = tata[nod]){
flux[tata[nod]][nod] += f_min;
flux[nod][tata[nod]] -= f_min; }
rez += f_min; } } } }
void add_muc(const int a, const int b, mat<int>& adiac){
adiac[a].push_back(b);
adiac[b].push_back(a); }
int main(){
ifstream f("harta.in");
ofstream g("harta.out");
int n;
f >> n;
const int surs = 0, outs = 1, ins = n+1, dest = 2*n+1, sz = 2*n+2;
mat<int> adiac(sz), cap(sz, vector<int>(sz, 0)), flux(sz, vector<int>(sz, 0));
for(int i = 0; i < n; ++i){
f >> cap[surs][outs+i] >> cap[ins+i][dest];
add_muc(surs, outs+i, adiac);
add_muc(ins+i, dest, adiac); }
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(i != j){
cap[outs+i][ins+j] = 1;
add_muc(outs+i, ins+j, adiac); } } }
const int m = flux_max(surs, dest, adiac, cap, flux);
g << m << '\n';
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
if(flux[i+outs][j+ins] == 1){
g << i+1 << ' ' << j+1 << '\n'; } } }
return 0; }