Pagini recente » Cod sursa (job #1413301) | Cod sursa (job #1616425) | Cod sursa (job #1433642) | Cod sursa (job #979320) | Cod sursa (job #2959451)
#include <bits/stdc++.h>
using namespace std;
int Nodes;
vector<int> *AdjacencyList, *AdjacencyInnerList;
// Cost matrix, flux matrix
long **flux, **cost;
bool FindUnsaturatedPath(int Source, int Destination, int Nodess, vector<int> *AdList, vector <int> *AdInList, long **flux, long **cost, int *dad, int *visited){
queue <int> Q;
int Node;
for(int i = 0; i <= Nodess; i++){
visited[i] = dad[i] = 0;
}
// Add the source in the queue
Q.push(Source);
// Mark the starting node as visited
visited[Source] = 1;
while(!Q.empty()){
Node = Q.front();
Q.pop();
// For the edges leaving from Node,
// check if it can be added more flux
for(auto NodeNext : AdList[Node]){
if( visited[NodeNext] != 1 && flux[Node][NodeNext] < cost[Node][NodeNext]){
dad[NodeNext] = Node;
// Check if the path reached the destination, and if it did
// exit the function
if(NodeNext == Destination)
return true;
Q.push(NodeNext);
visited[NodeNext] = 1;
}
}
// For the edges coming into Node,
// check if it can be added more flux
for(auto NodeNext: AdInList[Node]){
if( visited[NodeNext] != 1 && flux[Node][NodeNext] > 0){
dad[NodeNext] = -Node;
// Check if the path reached the destination, and if it did
// exit the function
if(NodeNext == Destination)
return true;
Q.push(NodeNext);
visited[NodeNext] = 1;
}
}
}
return false;
}
int main() {
////////////////////////////
/////// READING DATA ///////
////////////////////////////
int AllNodes, InDegree, OutDegree;
ifstream fin("harta.in");
fin >> AllNodes;
// Edmonds Karp Maximum Flow Adaptation
// We will have a bipartition:
// --> left set == right set, but there wont be edges
// from the same node to the same node
// Also, there will be 2 pseudo nodes:
// --> source: will have edge to every node, with the capacity of outer degree of that node
// --> destination: every node will have an edge that ends in 'destination' node with the value of their outer degree
Nodes = AllNodes * 2 + 2;
// Resize adjacency lists
AdjacencyList = new vector<int>[Nodes + 1];
AdjacencyInnerList = new vector<int>[Nodes + 1];
// Resize matrixs
flux = new long* [Nodes + 1];
cost = new long* [Nodes + 1];
int source = Nodes - 1, destination = Nodes, dest, maxflow = 0;
int *dad = new int[Nodes + 1], *visited = new int [Nodes + 1];
for(int i = 0; i <= Nodes; i++){
flux[i] = new long [Nodes + 1];
cost[i] = new long [Nodes + 1];
}
for(int i = 1; i <= AllNodes; i++){
fin >> OutDegree >> InDegree;
// Update the edge from source => NODEi
///////////////////////////////////////
AdjacencyList[source].push_back(i);
AdjacencyInnerList[i].push_back(source);
// Initialize matrixs
cost[source][i] = OutDegree;
flux[source][i] = 0;
// Update the edge from NODEi => destination
////////////////////////////////////////////
AdjacencyList[i + AllNodes].push_back(destination);
AdjacencyInnerList[destination].push_back(i + AllNodes);
// Initialize matrixs
cost[i + AllNodes][destination] = InDegree;
flux[i + AllNodes][destination] = 0;
}
fin.close();
// We add the maximul flow 1
// to the rest of the edge
for(int i = 1; i <= AllNodes; i++){
for(int j = 1; j <= AllNodes; j++){
if( i != j){
AdjacencyList[i].push_back(AllNodes + j);
AdjacencyInnerList[AllNodes + j].push_back(i);
// Initialize matrixs
cost[i][AllNodes + j] = 1;
flux[i][AllNodes + j] = 0;
}
}
}
// While we can discover unsaturated path
while(FindUnsaturatedPath(source, destination, Nodes, AdjacencyList, AdjacencyInnerList, flux, cost, dad, visited)){
// Calculate the minimum rezidual capacity in the path that the
// function has found
long MRC = LONG_MAX;
dest = destination;
while(dest != source){
// Edge leaving from dad
if(dad[dest] >= 0){
if( cost[dad[dest]][dest] - flux[dad[dest]][dest] < MRC)
MRC = cost[dad[dest]][dest] - flux[dad[dest]][dest];
dest = dad[dest];
} else{
// Edge coming into dad
if( flux[dest][-dad[dest]] < MRC)
MRC = flux[dest][-dad[dest]];
dest = -dad[dest];
}
}
dest = destination;
while(dest != source){
if(dad[dest] > 0){
flux[dad[dest]][dest] += MRC;
dest = dad[dest];
} else{
flux[dest][-dad[dest]] += MRC;
flux[dest][-dad[dest]] += MRC;
dest = -dad[dest];
}
}
maxflow += MRC;
}
ofstream fout("harta.out");
fout << maxflow << endl;
for(int i = 1; i <= AllNodes; i++){
for(int j = 1; j <= AllNodes; j++)
if(flux[i][j + AllNodes] == 1 && i != j){
fout << i << " " << j << endl;
}
}
fout.close();
return 0;
}