Pagini recente » Cod sursa (job #1263599) | Cod sursa (job #838483) | Cod sursa (job #1455021) | Cod sursa (job #639640) | Cod sursa (job #2958835)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int graf[201][201];
int tati[201];
bool vizitat[201];
bool bfs(int n)
{
queue<int> coada;
for(int i = 0; i <= n; i++)
{
vizitat[i] = false;
tati[i] = -1;
}
coada.push(0);
vizitat[0] = true;
while(coada.empty() == false)
{
int nod = coada.front();
coada.pop();
for(int i = 0; i <= n; i++)
{
if(graf[nod][i] > 0 && vizitat[i] == false)
{
coada.push(i);
vizitat[i] = true;
tati[i] = nod;
if(i == n)
{
return true;
}
}
}
}
return false;
}
int flux(int n)
{
int flux_maxim = 0;
while(bfs(n))
{
for(int i = 1; i < n; i++)
{
if(graf[i][n] > 0 && vizitat[i] == true)
{
int penultim = i;
vector<int> drum_c;
drum_c.push_back(n);
drum_c.push_back(penultim);
int tata = tati[penultim];
while(tata != -1)
{
drum_c.push_back(tata);
tata = tati[tata];
}
int bottleneck = 2;
for(int i = 1; i < drum_c.size(); i++)
{
bottleneck = min(bottleneck, graf[drum_c[i]][drum_c[i-1]]);
}
flux_maxim = flux_maxim + bottleneck;
for(int i = 1; i < drum_c.size(); i++)
{
graf[drum_c[i]][drum_c[i-1]] = graf[drum_c[i]][drum_c[i-1]] - bottleneck;
graf[drum_c[i-1]][drum_c[i]] = graf[drum_c[i-1]][drum_c[i]] + bottleneck;
}
}
}
}
return flux_maxim;
}
int main()
{
int n;
f >> n;
int a, b;
for(int i = 1; i <= n; i++)
{
f >> a >> b;
graf[0][i] = a;
graf[i + n][n * 2 + 1] = b;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i != j)
{
graf[i][j + n] = 1;
}
}
}
g << flux(2 * n + 1) << "\n";
for(int i = 1; i <= n; i++)
{
for(int j = n + 1; j <= n * 2; j++)
{
if(graf[j][i] != 0)
{
g << i << " " << j - n << "\n";
}
}
}
return 0;
}