Pagini recente » Cod sursa (job #271373) | Cod sursa (job #2297358) | Cod sursa (job #1406520) | Cod sursa (job #3176372) | Cod sursa (job #3181356)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
class Graf {
vector<vector<int>> muchii, val_muchii;
int nr_noduri;
vector<int> dsu;
int dsu_default;
vector<int> dsu_size;
public:
Graf(int n) : nr_noduri(n) {
muchii.assign(n + 1, vector<int>());
val_muchii.assign(n + 1, vector<int>(n+1, 0));
}
void add_muchie(int x, int y, int cost = 0) {
muchii[x].push_back(y);
val_muchii[x][y] = cost;
}
int bfs_maxflow(int n1, int n2, vector<int> &parents) {
queue<pair<int, int>> q;
q.push({n1, 1000});
parents[n1] = n1;
while (!q.empty()) {
int nod = q.front().first;
int cap_c = q.front().second;
q.pop();
for (auto &vecin: muchii[nod]) {
int r_cap = val_muchii[nod][vecin];
if (r_cap > 0 & parents[vecin] == -1) {
parents[vecin] = nod;
if (vecin == n2) return min(cap_c, r_cap);
q.push({vecin, min(cap_c, r_cap)});
}
}
}
return 0;
}
void maxflow(int n1, int n2, int n) {
int cap_min = 0;
vector<int> p(n2 + 1, -1);
while ((cap_min = bfs_maxflow(n1, n2, p))) {
int nodc = n2;
while (nodc != n1) {
val_muchii[p[nodc]][nodc] -= cap_min;
val_muchii[nodc][p[nodc]] += cap_min;
nodc = p[nodc];
}
p.assign(n2 + 1, -1);
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i != j && val_muchii[i][n+j] == 0){
fout << i << ' ' << j << '\n';
}
}
}
}
};
int main() {
std::cin.sync_with_stdio(0);
cin.tie(0);
int n, nr_muchii = 0;
fin >> n;
Graf g(2 * n + 1);
for (int i = 1; i <= n; i++) {
int iesiri, intrari;
fin >> iesiri >> intrari;
nr_muchii += iesiri;
g.add_muchie(0, i, iesiri);
g.add_muchie(n+i, 2 * n + 1, intrari);
for (int j = 1; j <= n; j++) {
if (i != j) {
g.add_muchie(i, n + j, 1);
g.add_muchie(n + j, i, 0);
}
}
}
fout << nr_muchii << '\n';
g.maxflow(0, 2 * n + 1, n);
return 0;
}