Pagini recente » Cod sursa (job #2242255) | Cod sursa (job #2248914) | Cod sursa (job #2868129) | Cod sursa (job #1353208) | Cod sursa (job #2956516)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("harta.in");
ofstream g ("harta.out");
vector <int> l[2001];
int n, c[2001][2001], fl[2001][2001], t[2001], v[2001];
int df (int vf)
{
int i;
stack <int> st;
st.push(vf);
v[vf] = 1;
t[vf] = 0;
while (!st.empty())
{
vf = st.top();
st.pop();
for (i = 0; i < l[vf].size(); i++)
{
if (!v[l[vf][i]] && fl[vf][l[vf][i]] < c[vf][l[vf][i]])
{
st.push(l[vf][i]);
v[l[vf][i]] = 1;
t[l[vf][i]] = vf;
if (l[vf][i] == 2 * n + 1) return 1;
}
}
}
return 0;
}
int main()
{int e, flux = 0, i, j, in, out, mn;
f >> n;
for (i = 1; i <= n; i++)
{
f >> in >> out;
l[0].push_back(i);
l[i].push_back(0);
c[0][i] = in;
l[i + n].push_back(2 * n + 1);
l[2 * n + 1].push_back(i + n);
c[i + n][2 * n + 1] = out;
}
for (i = 1; i <= n; i++)
for (j = 1; j <= n; j++)
if (i != j)
{
l[i].push_back(j + n);
l[j + n].push_back(i);
c[i][j + n] = 1;
}
while (df(0))
{
i = 2 * n + 1;
mn = 999999;
while (i > 0)
{
if (c[t[i]][i] - fl[t[i]][i] < mn)
mn = c[t[i]][i] - fl[t[i]][i];
i = t[i];
}
flux += mn;
i = 2 * n + 1;
while (i > 0)
{
fl[t[i]][i] += mn;
fl[i][t[i]] -= mn;
i = t[i];
}
for (i = 0; i <= 2 * n + 1; i++)
{
v[i] = 0;
t[i] = 0;
}
}
g << flux << '\n';
for (i = 1; i <= n; i++)
for (j = n + 1; j < 2 * n + 1; j++)
if (fl[i][j] == c[i][j] && fl[i][j] == 1)
g << i << ' ' << j - n << '\n';
return 0;
}