Pagini recente » Cod sursa (job #2718820) | Cod sursa (job #1380092) | Cod sursa (job #2353818) | Cod sursa (job #1532393) | Cod sursa (job #2327645)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, cost[402][402], f[402][402], t[402], m;
bool viz[402];
vector<int>g[402];
int s = 0, d = 201;
bool bfs () {
memset(viz, 0, sizeof(viz));
viz[s] = 1;
queue<int>q;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
if (u == d)
continue;
for (auto v: g[u]) {
if (cost[u][v] > f[u][v] && !viz[v]) {
viz[v] = 1;
q.push(v);
t[v] = u;
}
}
}
return viz[d];
}
void flux (int s, int d) {
int ans = 0;
while (bfs()) {
for (int i = 0; i < g[d].size(); i++) {
int v = g[d][i];
if (cost[v][d] > f[v][d] && viz[v]) {
t[d] = v;
int fmin = 1000000000;
for (int i = d; i != s; i = t[i])
fmin = min(fmin, cost[t[i]][i] - f[t[i]][i]);
for (int i = d; i != s; i = t[i]) {
f[t[i]][i] += fmin;
f[i][t[i]] -= fmin;
}
ans += fmin;
}
}
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++) {
int a, b;
fin >> a >> b;
g[s].push_back(i);
g[i].push_back(s);
cost[s][i] = a;
g[d].push_back(i + n);
g[i + n].push_back(d);
cost[i + n][d] = b;
m += a + b;
}
m /= 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j) {
g[i].push_back(j + n);
g[j + n].push_back(i);
cost[i][j + n] = 1;
}
flux(s, d);
fout << m << "\n";
for(int i = 1; i <= n; i++){
for(int j = 1;j <= n; j++) {
if(cost[i][j + n] == f[i][j + n] && cost[i][j + n])
fout << i << " " << j << "\n";
}
}
return 0;
}