Pagini recente » Cod sursa (job #836787) | Cod sursa (job #919632) | Cod sursa (job #618965) | Cod sursa (job #1551210) | Cod sursa (job #926123)
Cod sursa(job #926123)
#include <fstream>
#include <vector>
#include <queue>
#include <limits>
using namespace std;
#define NMAX 256
#define INFILE "harta.in"
#define OUTFILE "harta.out"
int ans, N;
vector<int> list[NMAX];
int capacities[NMAX][NMAX];
int flows[NMAX][NMAX];
void read()
{
int x, y;
ifstream fin(INFILE);
fin >> N;
for (int i = 1; i <= N; ++i)
{
fin >> x >> y;
capacities[2 * N + 1][i] = x;
capacities[i + N][2 * N + 2] = y;
list[2 * N + 1].push_back(i);
list[i].push_back(2 * N + 1);
list[2 * N + 2].push_back(i + N);
list[i + N].push_back(2 * N + 2);
}
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
if (i != j)
{
capacities[i][j + N] = 1;
list[i].push_back(j + N);
list[j + N].push_back(i);
}
}
}
fin.close();
}
int traverse()
{
int ans = 0;
bool seen[NMAX];
int papa[NMAX];
int x, y, f, c, m;
queue<int> nodes;
for (int i = 1; i <= 2 * N + 2; ++i)
{
papa[i] = 0;
seen[i] = false;
}
nodes.push(2 * N + 1);
seen[2 * N + 1] = true;
while (!nodes.empty())
{
x = nodes.front();
for (int i = 0; i < list[x].size(); ++i)
{
y = list[x][i];
if (seen[y] == true || y == 2 * N + 2)
{
continue;
}
f = flows[x][y];
c = capacities[x][y];
if (f < c)
{
seen[y] = true;
papa[y] = x;
nodes.push(y);
}
}
nodes.pop();
}
for (int i = 0; i < list[2 * N + 2].size(); ++i)
{
x = list[2 * N + 2][i];
f = flows[x][2 * N + 2];
c = capacities[x][2 * N + 2];
if (seen[x] == true && f < c)
{
m = numeric_limits<int>::max();
for (y = 2 * N + 2; x && m > 0; y = x, x = papa[x])
{
m = min(m, capacities[x][y] - flows[x][y]);
}
if (m <= 0)
{
continue;
}
for (y = 2 * N + 2, x = list[2 * N + 2][i]; x; y = x, x = papa[x])
{
flows[x][y] += m;
flows[y][x] -= m;
}
ans += m;
}
}
return ans;
}
void solve()
{
int f;
do
{
f = traverse();
ans += f;
}
while (f);
}
void write()
{
ofstream fout(OUTFILE);
fout << ans << '\n';
for (int i = 1; i <= N; ++i)
{
for (int j = 1; j <= N; ++j)
{
if (flows[i][N + j] > 0)
{
fout << i << ' ' << j << '\n';
}
}
}
fout.close();
}
int main()
{
read();
solve();
write();
}