Pagini recente » Cod sursa (job #98715) | Cod sursa (job #2651792) | Cod sursa (job #2895517) | Cod sursa (job #1220635) | Cod sursa (job #3187629)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAX_NODES = 100;
const int INF = 2e9;
int capacity[MAX_NODES * 2 + 5][MAX_NODES * 2 + 5], parent[MAX_NODES * 2 + 5], nodes, source, sink;
int bfs()
{
memset(parent, -1, sizeof(parent));
parent[source] = -2;
int u, v;
queue<int> q;
q.push(source);
while (!q.empty())
{
u = q.front();
q.pop();
if (u == sink)
continue;
for (v = 0; v <= sink; v++)
if (parent[v] == -1 && capacity[u][v] > 0)
{
parent[v] = u;
q.push(v);
}
}
return (parent[sink] != -1);
}
void updateFlow()
{
int node, flow;
flow = INF;
for (node = sink; parent[node] != -2; node = parent[node])
flow = min(flow, capacity[parent[node]][node]);
for (node = sink; parent[node] != -2; node = parent[node])
{
capacity[parent[node]][node] -= flow;
capacity[node][parent[node]] += flow;
}
}
void maxFlow()
{
int node;
while (bfs())
for (node = nodes + 1; node <= 2 * nodes; node++)
if (parent[node] != -1 && capacity[node][sink] > 0)
{
parent[sink] = node;
updateFlow();
}
}
int main()
{
ifstream fin("harta.in");
ofstream fout("harta.out");
int i, j, edges, x, y;
fin >> nodes;
edges = 0;
sink = 2 * nodes + 1;
for (i = 1; i <= nodes; i++)
{
fin >> x >> y;
capacity[0][i] = x;
capacity[nodes + i][sink] = y;
edges += x;
}
for (i = 1; i <= nodes; i++)
for (j = 1; j <= nodes; j++)
if (i != j)
capacity[i][nodes + j] = 1;
source = 0;
maxFlow();
fout << edges << endl;
for (i = 1; i <= nodes; i++)
for (j = 1; j <= nodes; j++)
if (i != j && capacity[i][nodes + j] == 0)
fout << i << " " << j << endl;
fin.close();
fout.close();
return 0;
}