Pagini recente » Cod sursa (job #640655) | Cod sursa (job #114233) | Cod sursa (job #895140) | Cod sursa (job #1347377) | Cod sursa (job #2964380)
#include<fstream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<int> a[205];
int n, s, d, sol, r[205][205], tata[205], in[205], out[205];
bool viz[205];
queue<int>q;
bool bfs()
{
int i, x, l;
for (i = 1;i <= n;i++)
viz[i] = 0, tata[i] = 0;
q.push(s);
viz[s] = 1;
while (!q.empty())
{
x = q.front();
q.pop();
l = a[x].size();
for (i = 0;i < l;i++)
if (viz[a[x][i]] == 0 && r[x][a[x][i]] > 0)
{
viz[a[x][i]] = 1;
tata[a[x][i]] = x;
q.push(a[x][i]);
}
}
return viz[d];
}
void flux_maxim()
{
int i, j, flow, l = a[d].size();
while (bfs() != 0)
{
for (i = 0;i < l;i++)
if (tata[a[d][i]] != 0 && r[a[d][i]][d] > 0)
{
flow = r[a[d][i]][d];
for (j = a[d][i];j != s;j = tata[j])
{
flow = min(flow, r[tata[j]][j]);
if (flow == 0)
break;
}
if (flow != 0)
{
r[a[d][i]][d] -= flow;
r[d][a[d][i]] += flow;
for (j = a[d][i];j != s;j = tata[j])
{
r[tata[j]][j] -= flow;
r[j][tata[j]] += flow;
}
sol += flow;
}
}
}
}
int main()
{
int i, sum = 0, j, l, nn;
fin >> n;
nn = n;
for (i = 1;i <= n;i++)
{
fin >> out[i] >> in[i];
sum += in[i];
}
s = 2 * n + 1;
d = 2 * n + 2;
for (i = 1;i <= n;i++)
{
a[s].push_back(i);
a[i].push_back(s);
a[i + n].push_back(d);
a[d].push_back(i + n);
r[s][i] = out[i];
r[i + n][d] = in[i];
for (j = 1;j <= n;j++)
if (i != j)
{
a[i].push_back(j + n);
a[j + n].push_back(i);
r[i][j + n] = 1;
}
}
n = n * 2 + 2;
flux_maxim();
fout << sum << '\n';
for (i = 1;i <= nn;i++)
{
l = a[i].size();
for (j = 0;j < l;j++)
if (a[i][j] <= 2 * nn && r[i][a[i][j]] == 0)
fout << i << " " << a[i][j] - nn << '\n';
}
return 0;
}