Pagini recente » Cod sursa (job #433416) | Cod sursa (job #2948455) | Cod sursa (job #1909681) | Cod sursa (job #2604095) | Cod sursa (job #3190113)
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <queue>
#include <climits>
#include <iostream>
#define MAX_NODES 505
using namespace std;
class Graph {
int n;
vector <vector <int>> adj;
int capacity[MAX_NODES][MAX_NODES];
int flux[MAX_NODES][MAX_NODES];
vector <int> parent;
vector <bool> viz;
public:
Graph(int n) : n(n), adj(n), viz(n), parent(n) {
memset(capacity, 0, sizeof(capacity));
memset(flux, 0, sizeof(flux));
}
void addEdge(int u, int v, int cap) {
adj[u].push_back(v);
adj[v].push_back(u);
capacity[u][v] = cap;
}
bool BFS(int src, int dst) {
fill(viz.begin(), viz.end(), 0);
queue <int> q;
viz[src] = 1;
q.push(src);
while (!q.empty()) {
int node = q.front();
q.pop();
for (auto it : adj[node]) {
if (!viz[it] && capacity[node][it] > flux[node][it]) {
viz[it] = 1;
parent[it] = node;
q.push(it);
}
}
}
return viz[dst];
}
int Flux(int src, int dst) {
int maxFlux = 0;
while (BFS(src, dst)) {
for (auto it : adj[dst]) {
if (viz[it] && capacity[it][dst] != flux[it][dst]) {
int node = dst, currFlux = INT_MAX;
while (node != src) {
int prev = parent[node];
currFlux = min(currFlux, capacity[prev][node] - flux[prev][node]);
//cout << node << " ";
node = prev;
}
//cout << endl;
if (currFlux == 0) continue;
node = dst;
while (node != src) {
int prev = parent[node];
flux[prev][node] += currFlux;
flux[node][prev] -= currFlux;
node = prev;
}
maxFlux += currFlux;
}
}
}
return maxFlux;
}
void printPadure(ostream& g) {
vector <pair <int, int>> sol;
for (int i = 1; i <= n / 2 - 1; ++i) {
for (int j = 1; j <= n / 2 - 1; ++j) {
if (i != j && flux[i][n / 2 + j - 1] == 1) {
sol.push_back({i, j});
}
}
}
g << sol.size() << "\n";
for (auto it : sol) {
g << it.first << " " << it.second << "\n";
}
}
};
int main() {
ifstream f("harta.in");
ofstream g("harta.out");
int n;
f >> n;
//cout << n << endl;
Graph G(2 * n + 2);
for (int i = 1; i <= n; ++i) {
int out, in;
f >> out >> in;
G.addEdge (0, i, out);
G.addEdge (n + i, 2 * n + 1, in);
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (i != j) {
G.addEdge(i, n + j, 1);
}
}
}
G.Flux(0, 2 * n + 1);
G.printPadure(g);
return 0;
}