Pagini recente » Cod sursa (job #1842390) | Cod sursa (job #2885272) | Cod sursa (job #1628382) | Cod sursa (job #1870705) | Cod sursa (job #3190755)
// https://www.infoarena.ro/problema/harta
#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#include <deque>
#include <queue>
#include <fstream>
#include <algorithm>
using namespace std;
struct Edge
{
int left, right;
};
class Graph
{
private:
static const int MAX_VERTICES = 100;
int noVertices;
int noEdges;
vector<vector<int>> neighbours;
vector<vector<int>> capacity;
vector<vector<int>> flow;
public:
Graph(const int &noVertices)
: noVertices(noVertices),
neighbours(noVertices + 1),
capacity(noVertices + 1, vector<int>(noVertices + 1, 0)),
flow(noVertices + 1, vector<int>(noVertices + 1, 0))
{
}
int getNoVertices()
{
return noVertices;
}
int getNoEdges()
{
return noEdges;
}
Graph& addNeighbours(const int& vertex1, const int& vertex2)
{
neighbours[vertex1].push_back(vertex2);
neighbours[vertex2].push_back(vertex1);
return *this;
}
Graph& addCapacity(const int& vertex, const int& neighbour, const int& capacity)
{
this->capacity[vertex][neighbour] = capacity;
return *this;
}
bool BFS(const int& source, const int& sink, vector<int>& parent)
{
parent = vector<int> (noVertices + 1, -2);
queue<int> que;
que.push(source);
parent[source] = -1;
while (!que.empty())
{
int curr_vertex = que.front();
que.pop();
if (curr_vertex == sink)
continue;
for (int neigh : neighbours[curr_vertex])
{
//atunci cand avem muchia inversa, capacitatea este 0
//deci cand flow-ul este 0, nu putem "intoarce" pe acolo ceva
//cand flow-ul este diferit de 0 (adica negativ) putem intoarce pe acolo ceva
if (parent[neigh] != -2 || flow[curr_vertex][neigh] == capacity[curr_vertex][neigh])
continue;
parent[neigh] = curr_vertex;
que.push(neigh);
}
}
return parent[sink] != -2;
}
int generateEdges(vector<Edge>& edges)
{
int maxFlow = 0;
vector<int> parent;
while(BFS(0, noVertices, parent))
{
for (int neigh : neighbours[noVertices])
{
int minFlowPath = INT_MAX;
int curr_vertex = noVertices;
int curr_parent = neigh;
for ( ; curr_vertex != 0; curr_vertex = curr_parent, curr_parent = parent[curr_vertex])
{
if (curr_parent == -2)
{
minFlowPath = 0;
break;
}
//de remarcat ca atunci cand avem o muchie de intoarcere, diferenta o sa fie
//0 - (un flux negativ), deci o sa comparam in continuare cu un numar pozitiv
if (capacity[curr_parent][curr_vertex] - flow[curr_parent][curr_vertex] < minFlowPath)
minFlowPath = capacity[curr_parent][curr_vertex] - flow[curr_parent][curr_vertex];
}
if (minFlowPath == 0)
continue;
maxFlow += minFlowPath;
curr_vertex = noVertices;
curr_parent = neigh;
for ( ; curr_vertex != 0; curr_vertex = curr_parent, curr_parent = parent[curr_vertex])
{
flow[curr_parent][curr_vertex] += minFlowPath;
flow[curr_vertex][curr_parent] -= minFlowPath;
}
}
}
edges = vector<Edge>();
for (int i = 1; i <= noVertices/2; i++)
for (int j = 1; j <= noVertices/2; j++)
if (flow[i][j + noVertices/2] == 1)
edges.push_back({i, j});
return edges.size();
}
};
int main()
{
int N, M;
ifstream fin ("harta.in");
fin>> N;
Graph graph(2 * N + 1);
for (int i=1; i<=N; i++)
{
int in, out;
fin >> in >> out;
graph.addNeighbours(0, i).addCapacity(0, i, in);
for (int j=1; j <= N; j++)
if (i != j)
graph.addNeighbours(i, j + N).addCapacity(i, j + N, 1);
graph.addNeighbours(i + N, 2 * N + 1).addCapacity(i + N, 2 * N + 1, out);
}
fin.close();
ofstream fout ("harta.out");
vector <Edge> edges;
fout << graph.generateEdges(edges) << "\n";
for (Edge& ed : edges)
fout << ed.left << " " << ed.right << "\n";
fout.close();
return 0;
}