Pagini recente » Cod sursa (job #2920990) | Cod sursa (job #1840150) | Cod sursa (job #2509883) | Cod sursa (job #2611818) | Cod sursa (job #3190134)
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<int> graph[205];
int vertices, source, destination, maxFlow, capacity[205][205], parent[205], inflow[205], outflow[205];
bool visited[205];
queue<int> bfsQueue;
bool bfs()
{
int current, neighbor, edgeCount;
for (int i = 1; i <= vertices; i++)
visited[i] = false, parent[i] = 0;
bfsQueue.push(source);
visited[source] = true;
while (!bfsQueue.empty())
{
current = bfsQueue.front();
bfsQueue.pop();
edgeCount = graph[current].size();
for (int i = 0; i < edgeCount; i++)
{
neighbor = graph[current][i];
if (!visited[neighbor] && capacity[current][neighbor] > 0)
{
visited[neighbor] = true;
parent[neighbor] = current;
bfsQueue.push(neighbor);
}
}
}
return visited[destination];
}
void maxflow()
{
int i, j, flow, edgeCount = graph[destination].size();
while (bfs())
{
for (i = 0; i < edgeCount; i++)
{
int currentNeighbor = graph[destination][i];
if (parent[currentNeighbor] != 0 && capacity[currentNeighbor][destination] > 0)
{
flow = capacity[currentNeighbor][destination];
for (j = currentNeighbor; j != source; j = parent[j])
{
flow = min(flow, capacity[parent[j]][j]);
if (flow == 0)
break;
}
if (flow != 0)
{
capacity[currentNeighbor][destination] -= flow;
capacity[destination][currentNeighbor] += flow;
for (j = currentNeighbor; j != source; j = parent[j])
{
capacity[parent[j]][j] -= flow;
capacity[j][parent[j]] += flow;
}
maxFlow += flow;
}
}
}
}
}
int main()
{
int i, totalflow = 0, j, edgeCount, nn;
fin >> vertices;
nn = vertices;
for (i = 1; i <= vertices; i++)
{
fin >> outflow[i] >> inflow[i];
totalflow += inflow[i];
}
source = 2 * vertices + 1;
destination = 2 * vertices + 2;
for (i = 1; i <= vertices; i++)
{
graph[source].push_back(i);
graph[i].push_back(source);
graph[i + vertices].push_back(destination);
graph[destination].push_back(i + vertices);
capacity[source][i] = outflow[i];
capacity[i + vertices][destination] = inflow[i];
for (j = 1; j <= vertices; j++)
if (i != j)
{
graph[i].push_back(j + vertices);
graph[j + vertices].push_back(i);
capacity[i][j + vertices] = 1;
}
}
vertices = vertices * 2 + 2;
maxflow();
fout << totalflow << '\n';
for (i = 1; i <= nn; i++)
{
edgeCount = graph[i].size();
for (j = 0; j < edgeCount; j++)
if (graph[i][j] <= 2 * nn && capacity[i][graph[i][j]] == 0)
fout << i << " " << graph[i][j] - nn << '\n';
}
return 0;
}