Pagini recente » Cod sursa (job #2566015) | Cod sursa (job #2958507) | Cod sursa (job #53799) | Cod sursa (job #788060) | Cod sursa (job #2415077)
#include <fstream>
#include <climits>
#include <cstring>
#include <vector>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define nmax 105
int n, x, y, m, A[nmax][nmax], fl, t[nmax], sursa, dest;
bool u[nmax];
vector<int> v[nmax];
void afis() {
for (int i = 1; i <= n; ++i) {
for (int j = n + 1; j < dest; ++j) if (A[j][i]) g << i << ' ' << j - n << '\n';
}
}
int bfs() {
memset(t,-1,sizeof(t));
memset(u,0,sizeof(u));
int Q[n], p(0), q(0);
Q[0] = sursa;
u[sursa] = 1;
while (p <= q) {
int nod = Q[p++];
for (int i = 0; i < v[nod].size(); ++i) {
int x = v[nod][i];
if (!u[x] && A[nod][x] > 0) {
t[x] = nod;
Q[++q] = x;
u[x] = 1;
}
}
}
if (t[dest] + 1) return 1;
return 0;
}
void muchii() {
for (int i = 1; i <= n; ++i) v[sursa].push_back(i), v[i].push_back(sursa);
for (int i = 1; i <= n; ++i)
for (int j = n + 1; j < dest; ++j) if (i+n != j) v[i].push_back(j), v[j].push_back(i), A[i][j] = 1;
for (int i = n + 1; i < dest; ++i) v[i].push_back(dest), v[dest].push_back(i);
}
int main()
{
f >> n;
sursa = 0, dest = 2 * n + 1;
muchii();
for (int i = 1; i <= n; ++i) {
f >> x >> y;
m += x;
A[sursa][i] = x;
A[n + i][dest] = y;
}
g << m << '\n';
fl = 0;
while (bfs()) {
for (int i = 1; i <= dest; ++i) {
if (t[i] + 1 && A[i][dest] > 0) {
int mini = INT_MAX;
mini = min(mini, A[i][dest]);
for (int j = i; j != sursa; j=t[j]) mini = min(mini,(A[t[j]][j]));
if (mini < 0) continue;
A[i][dest] -= mini;
for (int j = i; j != sursa; j=t[j]) A[t[j]][j] -= mini, A[j][t[j]] += mini;
fl += mini;
}
}
}
afis();
return 0;
}