Pagini recente » tema | Cod sursa (job #2905412) | Cod sursa (job #1987483) | Cod sursa (job #2157937) | Cod sursa (job #2422225)
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
using Matrix = vector<vector<int>>;
Matrix MakeMatrix(const vector<pair<int, int>> °rees)
{
int nodes = degrees.size();
Matrix mat(2 * nodes + 2, vector<int>(2 * nodes + 2, 0));
for (auto i = 1; i <= nodes; i += 1) {
mat[0][i] = degrees[i - 1].first;
mat[nodes + i][2 * nodes + 1] = degrees[i - 1].second;
}
for (auto i = 1; i <= nodes; i += 1) {
for (auto j = i + 1; j <= nodes; j += 1) {
mat[i][nodes + j] = 1;
mat[j][nodes + i] = 1;
}
}
return mat;
}
bool Bfs(const Matrix &mat, int source, int dest, vector<int> &pred)
{
pred.assign(mat.size(), -1);
vector<bool> visited(mat.size(), false);
queue<int> q;
visited[source] = true;
q.push(source);
while (!q.empty()) {
auto node = q.front();
q.pop();
for (size_t i = 0; i < mat.size(); i += 1) {
if (mat[node][i] > 0 && !visited[i]) {
visited[i] = true;
pred[i] = node;
q.push(i);
}
}
}
return visited[dest];
}
int FindMinCapacity(const Matrix &mat, int node, int prev, const vector<int> &pred)
{
auto res = mat[node][prev];
while (node != -1) {
res = min(res, mat[node][prev]);
prev = node;
node = pred[node];
}
return res;
}
void Flow(Matrix &mat, int node, int prev, const vector<int> &pred)
{
auto min_capacity = FindMinCapacity(mat, node, prev, pred);
if (min_capacity <= 0) {
return;
}
while (node != -1) {
mat[node][prev] -= min_capacity;
mat[prev][node] += min_capacity;
prev = node;
node = pred[node];
}
}
void FindMaxFlow(Matrix &mat, int source, int dest)
{
vector<int> pred;
while (Bfs(mat, source, dest, pred)) {
for (size_t i = 0; i < mat.size(); i += 1) {
if (mat[i][dest] > 0) {
Flow(mat, i, dest, pred);
}
}
}
}
vector<pair<int, int>> Solve(const vector<pair<int, int>> °rees)
{
auto mat = MakeMatrix(degrees);
auto nodes = degrees.size();
FindMaxFlow(mat, 0, 2 * nodes + 1);
vector<pair<int, int>> edges;
for (size_t i = 1; i <= nodes; i += 1) {
for (size_t j = 1; j <= nodes; j += 1) {
if (mat[nodes + j][i] > 0) {
edges.push_back({i, j});
}
}
}
return edges;
}
int main()
{
ifstream fin("harta.in");
ofstream fout("harta.out");
int nodes;
fin >> nodes;
vector<pair<int, int>> degrees(nodes);
for (auto &p : degrees) {
fin >> p.first >> p.second;
}
auto res = Solve(degrees);
fout << res.size() << "\n";
for (const auto &p : res) {
fout << p.first << " " << p.second << "\n";
}
return 0;
}