Pagini recente » Cod sursa (job #1647224) | Cod sursa (job #2859198) | Cod sursa (job #427706) | Cod sursa (job #264176) | Cod sursa (job #2962270)
#include <fstream>
#include <vector>
#include <iostream>
#include <string.h>
#include <string>
#include <sstream>
#include <climits>
#include <queue>
using namespace std;
int n, maxFlow;
int nodeCount;
vector<vector<pair<int, pair<int, int>>>> adjList;
vector<vector<int>> capacityMap;
vector<pair<int,int>> parentMap;
ifstream myIn("harta.in");
ofstream myOut("harta.out");
void ReadInputs() {
myIn >> n;
nodeCount = 2 * n + 2;
adjList.resize(nodeCount, {});
parentMap.resize(nodeCount, { -1,-1 });
int in, out;
for (int i = 1; i <= n; i++) {
myIn >> in >> out;
int indexA = adjList[0].size();
int indexB = adjList[nodeCount - 1].size();
int indexC1 = adjList[i].size();
int indexC2 = adjList[n + i].size();
adjList[0].push_back({ i,{ in,indexC1 } });
adjList[i].push_back({ 0,{ 0,indexA } });
adjList[nodeCount-1].push_back({ n + i,{ 0,indexC2} });
adjList[n + i].push_back({ nodeCount - 1,{ out,indexB } });
}
for (int nodeA = 1; nodeA <= n; nodeA++) {
for (int nodeB = 1; nodeB <= n; nodeB++) {
if (nodeA == nodeB) continue;
int offsetB = n + nodeB;
int indexA = adjList[nodeA].size();
int indexB = adjList[offsetB].size();
adjList[nodeA].push_back({ offsetB,{ 1,indexB } });
adjList[offsetB].push_back({ nodeA,{ 0,indexA } });
}
}
//for (int node = 0; node < nodeCount; node++) {
// if (node == nodeCount - 1) {
// cout << "f: ";
// }
// else if (node == 0) {
// cout << "s: ";
// }
// else {
// cout << node << ": ";
// }
// for (int i = 0; i < adjList[node].size(); i++) {
// int newNode = adjList[node][i].first;
// if (newNode == nodeCount - 1) {
// cout << "f ";
// }
// else if (newNode == 0) {
// cout << "s ";
// }
// else {
// cout << newNode << " ";
// }
// }
// cout << "\n";
//}
//cout << "\n";
}
bool BFS() {
for (int i = 0; i < parentMap.size(); i++) {
parentMap[i].first = -1; parentMap[i].second = -1;
}
queue<int> q;
q.push(0);
while (not q.empty()) {
int currentNode = q.front();
q.pop();
if (currentNode == nodeCount - 1) {
return true;
}
for (int i = 0; i < adjList[currentNode].size(); i++) {
auto nodeData = adjList[currentNode][i];
int nextNode = nodeData.first;
int capacity = nodeData.second.first;
if ((parentMap[nextNode].first == -1) && (capacity > 0)) {
q.push(nextNode);
parentMap[nextNode] = { currentNode,i };
}
}
}
return false;
}
void EdmondsKarp() {
int x = 0;
while (BFS()) {
for (int linkIndex = 0; linkIndex < adjList[nodeCount - 1].size(); linkIndex++) {
auto linkData = adjList[nodeCount - 1][linkIndex];
int sinkNode = linkData.first;
if (parentMap[sinkNode].first != -1) {
parentMap[nodeCount - 1].first = sinkNode;
parentMap[nodeCount - 1].second = linkData.second.second;
int minFlow = INT_MAX;
for (int node = (nodeCount - 1); node != 0; node = parentMap[node].first) {
int adjNode = parentMap[node].first;
auto prevNodeLink = adjList[adjNode][parentMap[node].second];
minFlow = min(minFlow, prevNodeLink.second.first);
}
if (minFlow <= 0) continue;
for (int node = (nodeCount - 1); node != 0; node = parentMap[node].first) {
int adjNode = parentMap[node].first;
(adjList[node][(adjList[adjNode][parentMap[node].second]).second.second]).second.first += minFlow;
(adjList[adjNode][parentMap[node].second]).second.first -= minFlow;
}
maxFlow += minFlow;
}
}
}
}
void Output() {
myOut << maxFlow << '\n';
for (int i = 0; i < parentMap.size(); i++) {
parentMap[i].first = 0;
}
parentMap[0].first = 1;
parentMap[nodeCount - 1].first = 1;
for (int node = 1; node <= n; node++) {
for (int i = 0; i < adjList[node].size(); i++) {
int newNode = adjList[node][i].first;
if (((newNode - n) != node) && (newNode != 0) && (adjList[node][i].second.first != 1))
myOut << node << ' ' << newNode - n << '\n';
}
parentMap[node].first = 1;
}
}
int main() {
ReadInputs();
EdmondsKarp();
Output();
}