Pagini recente » Borderou de evaluare (job #12271) | Cod sursa (job #3190205)
#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <fstream>
using namespace std;
#define NMAX 256
vector<int> Graph[NMAX];
int NumCities, DestinationNode;
int Capacities[NMAX][NMAX];
int Previous[NMAX + 4];
// Algoritmul Bellman-Ford pentru gasirea drumurilor de crestere
bool BellmanFord()
{
vector<int>::iterator it;
memset(Previous, -1, sizeof(Previous));
int node;
queue<int> Queue;
Queue.push(0);
while (!Queue.empty())
{
node = Queue.front();
if (node == DestinationNode)
break;
// Parcurgere noduri adiacente pentru gasirea drumurilor de crestere
for (it = Graph[node].begin(); it != Graph[node].end(); ++it)
{
if (Previous[*it] == -1 && Capacities[node][*it] > 0)
{
Queue.push(*it);
Previous[*it] = node;
}
}
Queue.pop();
}
if (node != DestinationNode)
return true;
// Modificarea fluxului pe drumurile de crestere gasite
for (node = DestinationNode; node; node = Previous[node])
{
--Capacities[Previous[node]][node];
++Capacities[node][Previous[node]];
}
return false;
}
ofstream fout("harta.out");
// Afisarea drumurilor cu capacitati nule
void ShowPaths()
{
int i, j;
for (i = 1; i <= NumCities; ++i)
for (j = 1; j <= NumCities; ++j)
if (i != j && !Capacities[i][j + NumCities])
{
fout << i << " " << j << "\n";
}
}
// Rezolvarea problemei utilizand algoritmul de flux maxim
void SolveProblem()
{
int Answer = 0;
// Gasirea repetata a drumurilor de crestere pana cand nu mai exista
while (!BellmanFord())
++Answer;
// Afisarea rezultatelor
fout << Answer << "\n";
ShowPaths();
}
int main()
{
ifstream fin("harta.in");
// Citirea numarului de orase
fin >> NumCities;
DestinationNode = (NumCities << 1) + 2;
int i, j;
int Outgoing, Incoming;
// Initializarea grafului si capacitatilor
for (i = 1; i <= NumCities; ++i)
{
fin >> Outgoing >> Incoming;
Graph[i].push_back(0);
Graph[0].push_back(i);
Capacities[0][i] = Outgoing;
Graph[i + NumCities].push_back(DestinationNode);
Graph[DestinationNode].push_back(i + NumCities);
Capacities[i + NumCities][DestinationNode] = Incoming;
// Adaugarea drumurilor intre orase cu capacitati
for (j = 1; j <= NumCities; ++j)
{
if (j != i)
{
Graph[i].push_back(j + NumCities);
Graph[j + NumCities].push_back(i);
Capacities[i][j + NumCities] = 1;
Capacities[j + NumCities][i] = 0;
}
}
}
SolveProblem();
fin.close();
fout.close();
return 0;
}