Pagini recente » Cod sursa (job #2949985) | Cod sursa (job #1597482) | Cod sursa (job #2206074) | Cod sursa (job #610151) | Cod sursa (job #2962418)
#include <bits/stdc++.h>
using namespace std;
///ex3-a infoarena harta
ifstream fin("harta.in");
ofstream fout("harta.out");
int capacitate[202][202];
vector<int> viz, tata;
int n, s = 0, t;
bool BFS()
{
viz.clear();
tata.clear();
viz.resize(t + 1, 0);
tata.resize(t + 1, 0);
queue<int> coada;
coada.push(s);
viz[s] = 1;
while(!coada.empty())
{
int nod = coada.front();
coada.pop();
if(nod == t)
return true;
for(int i = 1; i <= t; i++)
{
if(!viz[i] && capacitate[nod][i] > 0)
{
viz[i] = 1;
tata[i] = nod;
coada.push(i);
}
}
}
return false;
}
int minFlow(){
int minflux = INT_MAX;
for(int nod = t; nod != s; nod = tata[nod])
{
minflux = min(minflux, capacitate[tata[nod]][nod]);
}
return minflux;
}
void ex3(){
fin >> n;
t = 2 * n + 1;
for(int i = 1; i <= n; i++)
{
int x, y;
fin >> x >> y;
capacitate[s][i] = x;
capacitate[i+n][t] = y;
for(int j = 1; j <= n; j++)
if(i != j)
capacitate[i][j+n] = 1;
}
int maxflow = 0;
while(BFS()){
for(int i = n + 1 ; i <= 2 * n; i++){
if(!viz[i] || capacitate[i][t] == 0)
continue;
tata[t] = i;
int minflux = minFlow();
if(minflux == 0)
continue;
for(int nod = t; nod != s; nod = tata[nod])
{
capacitate[tata[nod]][nod] -= minflux;
capacitate[nod][tata[nod]] += minflux;
}
maxflow += minflux;
}
}
fout << maxflow << "\n";
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
if (capacitate[i][j + n] == 0 && i != j)
fout << i << " " << j << "\n";
}
}
int main() {
ex3();
return 0;
}