Pagini recente » Cod sursa (job #3151013) | Cod sursa (job #1468459) | Cod sursa (job #1668524) | Cod sursa (job #1730810) | Cod sursa (job #2098467)
#include <bits/stdc++.h>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
const int MaxN = 205;
int n, m, s, d, flow[MaxN][MaxN], cap[MaxN][MaxN], from[MaxN];
bool bfs()
{
queue<int> q;
bool viz[MaxN];
memset(viz, 0, sizeof(viz));
memset(from, 0, sizeof(from));
q.push(s);
viz[s] = 1;
while (!q.empty() && !viz[d])
{
int node = q.front();
for (int son = 1; son <= d; ++son)
if (son != node && !viz[son] && flow[node][son] < cap[node][son])
{
from[son] = node;
viz[son] = 1;
q.push(son);
}
q.pop();
}
return viz[d];
}
int main()
{
f >> n;
s = 2 * n + 3;
d = 2 * n + 2;
for (int i = 1; i <= n; ++i)
for (int j = i + 1; j <= n; ++j)
{
cap[2 * i][2 * j + 1] = cap[2 * j][2 * i + 1] = 1;
}
for (int i = 1; i <= n; ++i)
{
int a, b;
f >> a >> b;
m += a;
cap[2 * i + 1][d] = b;
cap[s][2 * i] = a;
}
while (bfs())
{
for (int i = 1; i <= s; ++i)
if (from[i] && flow[i][d] < cap[i][d])
{
from[d] = i;
int node = d, mini = 10000;
while (from[node])
{
mini = min(mini, cap[from[node]][node] - flow[from[node]][node]);
node = from[node];
}
node = d;
while (from[node])
{
flow[from[node]][node] += mini;
flow[node][from[node]] -= mini;
node = from[node];
}
}
}
g << m <<'\n';
for (int i = 1; i < d; ++i)
for (int j = 1; j < d; ++j) if (flow[i][j] > 0) g << i / 2 << ' ' << j / 2 << '\n';
return 0;
}