Pagini recente » Cod sursa (job #2414776) | Cod sursa (job #2528980) | Cod sursa (job #3254217) | Cod sursa (job #522957) | Cod sursa (job #3188087)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
std::ifstream fin("harta.in");
std::ofstream fout("harta.out");
std::vector<std::vector<int>> F(210, std::vector<int>(210, 0));
std::vector<std::vector<int>> C(210, std::vector<int>(210, 0));
std::vector<int> EDGE_FLOW(210, 0);
std::vector<int>FROM_TO(210, -1);
std::vector<std::vector<int>> ADJ_LIST(210);
int BFS(int start_vertex, int finish_vertex)
{
std::fill(FROM_TO.begin(), FROM_TO.end(), -1);
std::fill(EDGE_FLOW.begin(), EDGE_FLOW.end(), 0);
std::queue<int> QUEUE;
QUEUE.push(start_vertex);
EDGE_FLOW[start_vertex] = INT_MAX;
FROM_TO[start_vertex] = -2;
while(!QUEUE.empty())
{
int vertex = QUEUE.front();
QUEUE.pop();
for(int adj_vertex : ADJ_LIST[vertex])
{
if(FROM_TO[adj_vertex] == -1)
{
if(C[vertex][adj_vertex] - F[vertex][adj_vertex] > 0)
{
FROM_TO[adj_vertex] = vertex;
EDGE_FLOW[adj_vertex] = std::min(EDGE_FLOW[vertex],
C[vertex][adj_vertex] - F[vertex][adj_vertex]);
if(adj_vertex == finish_vertex) return EDGE_FLOW[adj_vertex];
QUEUE.push(adj_vertex);
}
}
}
}
return 0;
}
int EK(int start_vertex, int finish_vertex)
{
int MAX_FLOW = 0;
std::fill(F.begin(), F.end(), std::vector<int>(210, 0));
while(true) {
int FLOW = BFS(start_vertex, finish_vertex);
if (FLOW == 0) {break;}
MAX_FLOW = MAX_FLOW + FLOW;
int vertex = finish_vertex;
while (vertex != start_vertex)
{
int prev_vertex = FROM_TO[vertex];
F[prev_vertex][vertex] += FLOW;
F[vertex][prev_vertex] -= FLOW; //rezid
vertex = prev_vertex;
}
}
return MAX_FLOW;
}
int main()
{
int N;
fin >> N;
int S = 0;
int E = 2 * N + 1;
for(int i = 1 ; i <= N; i++)
{
int OUTWARDS, INWARDS;
fin >> OUTWARDS >> INWARDS;
C[S][i] = OUTWARDS;
C[i + N][E] = INWARDS;
ADJ_LIST[S].emplace_back(i);
ADJ_LIST[N + i].emplace_back(E);
for(int j = 1; j <= N; j++)
{
if(i != j) //excludem buclele
{
C[i][j + N] = 1;
ADJ_LIST[i].emplace_back(j + N);
ADJ_LIST[j + N].emplace_back(i);
}
}
}
int MAX_FLOW = EK(S, E);
fout << MAX_FLOW << "\n";
for(int i = 1; i <= N; i++)
{
for(int j = 1; j <= N; j++)
{
if(F[i][j + N] > 0)
{
fout << i << " " << j << "\n";
}
}
}
fin.close();
fout.close();
return 0;
}