Pagini recente » Cod sursa (job #3169546) | Cod sursa (job #803607) | Cod sursa (job #113539) | Cod sursa (job #727433) | Cod sursa (job #2956313)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
class Graph
{
private:
vector<int> parent;
vector<bool> seen;
vector<vector<int>> capacityFromXtoY;
int noOfVerticesInFirstSet;
int noOfVertices;
int lastVertex;
int maxFlow;
public:
Graph(int n, int n1)
{
noOfVertices = n+1;
lastVertex = n+1;
noOfVerticesInFirstSet = n1;
capacityFromXtoY.resize(n+2);
for (int i = 0; i <= n+1; i++)
{
capacityFromXtoY[i].resize(n+2, 0);
}
parent.resize(n+1, 0);
seen.resize(n+1, 0);
maxFlow = 0;
}
void readEdges()
{
for(int i = 1; i <= noOfVerticesInFirstSet; i++)
{
int n, m;
fin >> n >> m;
capacityFromXtoY[0][i] = n;
capacityFromXtoY[noOfVerticesInFirstSet + i][lastVertex] = m;
for (int j = noOfVerticesInFirstSet+1; j < noOfVertices; j++)
{
if(i != j-noOfVerticesInFirstSet)
{
capacityFromXtoY[i][j] = 1;
}
}
}
}
bool bfs()
{
seen.assign(noOfVertices + 2, 0);
parent.assign(noOfVertices + 2, 0);
queue<int> que;
que.push(0);
seen[0] = true;
parent[0] = 0;
while (!que.empty())
{
int front = que.front();
que.pop();
if(front != lastVertex)
{
for(int i = 1; i <= noOfVertices; i++)
{
if(seen[i] == false && capacityFromXtoY[front][i] > 0)
{
que.push(i);
parent[i] = front;
seen[i] = true;
}
}
}
}
return seen[lastVertex];
}
void getMaxFlow()
{
while (this->bfs())
{
for(int i = noOfVerticesInFirstSet + 1 ; i < noOfVertices; i++)
{
if(seen[i] && capacityFromXtoY[i][lastVertex]>0)
{
parent[lastVertex] = i;
int localMaxFlow = 1<<30;
int vrtx = lastVertex;
while(vrtx != 0)
{
localMaxFlow = min(localMaxFlow, capacityFromXtoY[parent[vrtx]][vrtx]);
vrtx = parent[vrtx];
}
if(localMaxFlow == 0)
{
continue;
}
vrtx = lastVertex;
while(vrtx != 0)
{
capacityFromXtoY[parent[vrtx]][vrtx] -= localMaxFlow;
capacityFromXtoY[vrtx][parent[vrtx]] += localMaxFlow;
vrtx = parent[vrtx];
}
maxFlow += localMaxFlow;
}
}
}
// return maxFlow;
fout<<maxFlow<<"\n";
}
void output()
{
for(int i = 1; i <= noOfVerticesInFirstSet; i++)
{
for(int j = noOfVerticesInFirstSet+1; j < noOfVertices; j++)
{
if(capacityFromXtoY[i][j] == 0 && i != j - noOfVerticesInFirstSet)
{
fout<<i<<" "<< j - noOfVerticesInFirstSet<<"\n";
}
}
}
}
};
int main()
{
int n;
fin>>n;
Graph graph (n*2, n);
graph.readEdges();
graph.getMaxFlow();
graph.output();
return 0;
}