Pagini recente » Cod sursa (job #2321602) | Cod sursa (job #976274) | Cod sursa (job #2360362) | Cod sursa (job #245127) | Cod sursa (job #3186829)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
class graf_flux
{
int n;
std::vector<std::vector<int>> adj_list;
std::vector<std::vector<int>> adj_list_rev;
std::vector<std::vector<int>> capacitati;
std::vector<std::vector<int>> flux;
int sursa;
int destinatie;
std::vector<int> tata;
public:
graf_flux(int n_, const std::vector<std::vector<int>>& adj_list_,
const std::vector<std::vector<int>>& capacitati_, int sursa_, int destinatie_);
const std::vector<int>& get_tata()const;
bool construieste_lant_nesaturat();
int flux_muchie(int x, int y) const;
void update_flux();
void print_cap()const{
std::cout<<"\n-------------------------\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
std::cout<<capacitati[i][j]<<" ";
std::cout<<"\n";
}
std::cout<<"-------------------------\n";
}
void print_flux()const{
std::cout<<"\n-------------------------\n";
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
std::cout<<flux[i][j]<<" ";
std::cout<<"\n";
}
std::cout<<"-------------------------\n";
}
};
int main()
{
std::ifstream f("harta.in");
std::ofstream h("harta.out");
int n = 0;
f >> n;
int din = 0;
int dout = 0;
std::vector<std::vector<int>> adj_list(2*n+2);
std::vector<std::vector<int>> cap(2*n + 2, std::vector<int>(2*n + 2, 1));
for(int i=0;i<2*n + 2;i++)
cap[i][i]=0;
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(i!=j)
adj_list.at(i).push_back(j);
for(int i=1;i<=n;i++)
{
f >> dout >> din;
adj_list[0].push_back(i);
adj_list[i+n].push_back(2*n + 1);
cap[0][i] = din;
cap[i+n][2*n + 1] = dout;
}
graf_flux g(2*n + 2, adj_list, cap,0, 2*n + 1);
int flux = 0;
std::vector<std::vector<int>> muchii;
while(g.construieste_lant_nesaturat())
{
g.update_flux();
auto tata = g.get_tata();
int node = 2*n + 1;
int y = tata[node];
int x = tata[y];
flux += g.flux_muchie(x,y);
muchii.push_back(std::vector<int>{x, y-n});
}
h << flux << "\n";
for(auto i: muchii)
h << i[0] << " " << i[1] << "\n";
f.close();
h.close();
return 0;
}
graf_flux::graf_flux(int n_, const std::vector<std::vector<int>>& adj_list_, const std::vector<std::vector<int>>& capacitati_,
int sursa_, int destinatie_): n(n_), adj_list(adj_list_), capacitati(capacitati_), sursa(sursa_), destinatie(destinatie_)
{
flux = std::vector<std::vector<int>>(n, std::vector<int>(n, 0));
adj_list_rev = std::vector<std::vector<int>>(n);
for(int i=0; i<n; ++i)
for(auto j: adj_list[i])
adj_list_rev[j].push_back(i);
}
const std::vector<int>& graf_flux::get_tata()const
{
return tata;
}
bool graf_flux::construieste_lant_nesaturat()
{
std::vector<bool> viz(n, false);
tata = std::vector<int>(n, INT_MAX);
std::queue<int> q;
q.push(sursa);
viz[sursa] = true;
tata[sursa] = sursa;
while(!q.empty())
{
// std::cout<<1;
int node = q.front();
q.pop();
for(auto vec: adj_list[node])
if(!viz[vec] && capacitati[node][vec] - flux[node][vec] > 0)
{
q.push(vec);
// std::cout<<"pushed "<<vec<<"\n";
tata[vec] = node;
viz[vec] = true;
if(vec == destinatie) return true;
}
for(auto vec: adj_list_rev[node])
if(!viz[vec] && flux[vec][node] > 0)
{
q.push(vec);
tata[vec] = -node;
viz[vec] = true;
if(vec == destinatie) return true;
}
}
// std::cout<<"niciun drum de crestere!!!\n";
return false;
}
int graf_flux::flux_muchie(int x, int y) const
{
return flux[x][y];
}
void graf_flux::update_flux()
{
int node = destinatie;
int f_min = INT_MAX;
for(int i=0;i<n;i++)
std::cout<<i <<" <- "<<tata[i]<<"\n";
while(tata[node] != node)
{
if(tata[node] < 0)
f_min = std::min(f_min, flux[-tata[node]][node]);
else
f_min = std::min(f_min, capacitati[tata[node]][node] - flux[tata[node]][node]);
node = tata[node];
}
node = destinatie;
while(tata[node] != node)
{
if(tata[node] < 0)
flux[-tata[node]][node] -= f_min;
else
flux[tata[node]][node] += f_min;
node = tata[node];
}
}