Pagini recente » Cod sursa (job #2122571) | Cod sursa (job #2270641) | Istoria paginii runda/simulare-cartita-33 | Cod sursa (job #1218764) | Cod sursa (job #1253381)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f ("harta.in");
ofstream g ("harta.out");
const int NMAX = 2 * 100 + 2;
int n, sursa, destinatie;
bool vizitat[NMAX];
int tata[NMAX];
int cost[NMAX][NMAX];
int F[NMAX][NMAX];
vector <int> graf[NMAX];
vector < pair <int, int> > sol;
void initializeaza() {
f >> n;
sursa = 0;
destinatie = 2 * n + 1;
int in, out;
for (int i = 1; i <= n; i++) {
f >> in >> out;
graf[sursa].push_back(i);
graf[i].push_back(sursa);
cost[sursa][i] += in;
graf[i + n].push_back(destinatie);
graf[destinatie].push_back(i + n);
cost[i + n][destinatie] += out;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j) {
graf[i].push_back(j + n);
graf[j + n].push_back(i);
cost[i][j + n]++;
}
}
bool BFS() {
int i, nod, fiu, l;
queue <int> Q;
for (int i = 0; i <= NMAX; i++) vizitat[i] = false, tata[i] = 0;
Q.push(sursa); vizitat[sursa] = true;
while (!Q.empty()) {
nod = Q.front();
Q.pop();
if (nod != destinatie) {
int l = graf[nod].size();
for (int i = 0; i < l; i++) {
fiu = graf[nod][i];
if (!vizitat[fiu] && F[nod][fiu] < cost[nod][fiu]) {
Q.push(fiu);
vizitat[fiu] = true;
tata[fiu] = nod;
}
}
}
}
return vizitat[destinatie];
}
void flux() {
int l, nod, rez, ant;
while(BFS()) {
l = graf[destinatie].size();
for (int i = 0; i < l; i++) {
nod = graf[destinatie][i];
rez = cost[nod][destinatie] - F[nod][destinatie];
while (nod != sursa) {
ant = tata[nod];
rez = min(rez, cost[ant][nod] - F[ant][nod]);
nod = ant;
}
if (rez == 0) continue;
nod = graf[destinatie][i];
F[nod][destinatie] += rez;
F[destinatie][nod] -= rez;
while (nod != sursa) {
ant = tata[nod];
F[ant][nod] += rez;
F[nod][ant] -= rez;
nod = ant;
}
// sol += rez;
}
}
// cout << sol << '\n';
}
void scrie() {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (F[i][j + n] > 0) sol.push_back(make_pair(i, j));
g << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++) g << sol[i].first << ' ' << sol[i].second << '\n';
}
int main() {
initializeaza();
flux();
scrie();
}