Pagini recente » Cod sursa (job #262897) | Cod sursa (job #1357713) | Cod sursa (job #354381) | Cod sursa (job #2785021) | Cod sursa (job #3188837)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#include <cstring>
using namespace std;
const int MAX_N = 210;
const int INF = INT_MAX;
int capacity[MAX_N][MAX_N];
int flowPassed[MAX_N][MAX_N];
vector<int> graph[MAX_N];
int parentsList[MAX_N];
int currentPathCapacity[MAX_N];
int bfs(int startNode, int endNode) {
memset(parentsList, -1, sizeof(parentsList));
memset(currentPathCapacity, 0, sizeof(currentPathCapacity));
queue<int> q;
q.push(startNode);
parentsList[startNode] = -2;
currentPathCapacity[startNode] = INF;
while (!q.empty()) {
int currentNode = q.front();
q.pop();
for (int to : graph[currentNode]) {
if (parentsList[to] == -1) {
if (capacity[currentNode][to] - flowPassed[currentNode][to] > 0) {
parentsList[to] = currentNode;
currentPathCapacity[to] = min(currentPathCapacity[currentNode],
capacity[currentNode][to] - flowPassed[currentNode][to]);
if (to == endNode) {
return currentPathCapacity[endNode];
}
q.push(to);
}
}
}
}
return 0;
}
int edmondsKarp(int startNode, int endNode) {
int maxFlow = 0;
memset(flowPassed, 0, sizeof(flowPassed));
while (true) {
int flow = bfs(startNode, endNode);
if (flow == 0) {
break;
}
maxFlow += flow;
int currentNode = endNode;
while (currentNode != startNode) {
int previousNode = parentsList[currentNode];
flowPassed[previousNode][currentNode] += flow;
flowPassed[currentNode][previousNode] -= flow;
currentNode = previousNode;
}
}
return maxFlow;
}
int main() {
ifstream fin("harta.in");
ofstream fout("harta.out");
int n;
fin >> n;
int source = 0, sink = 2 * n + 1;
for (int i = 1; i <= n; ++i) {
int out, in;
fin >> out >> in;
capacity[source][i] = out;
capacity[i + n][sink] = in;
graph[source].push_back(i);
graph[i + n].push_back(sink);
for (int j = 1; j <= n; ++j) {
if (i != j) {
capacity[i][j + n] = 1;
graph[i].push_back(j + n);
graph[j + n].push_back(i);
}
}
}
int maxFlow = edmondsKarp(source, sink);
fout << maxFlow << endl;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
if (flowPassed[i][j + n] > 0) {
fout << i << " " << j << endl;
}
}
}
fin.close();
fout.close();
return 0;
}