Pagini recente » Cod sursa (job #2950575) | Cod sursa (job #2707021) | Cod sursa (job #86235) | Cod sursa (job #2242094) | Cod sursa (job #3190215)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
class Graf {
int n;
vector<vector<int>> L;
vector<vector<int>> resid;
vector<int> tata;
bitset<1005> f;
public:
Graf(int n, vector<vector<int>>& L, vector<vector<int>>& resid) : n(n), L(L), resid(resid) {
tata.resize(n + 1);
f.reset();
}
bool bfs(int s, int d) {
f.reset(); f[s] = 1; tata[s] = -1;
deque<int> c; c.push_back(s);
while (!c.empty()) {
int nod = c.front(); c.pop_front();
for (int i=0; i<L[nod].size(); i++) {
int vecin = L[nod][i];
if (!f[vecin] && resid[nod][vecin] > 0) {
c.push_back(vecin);
f[vecin] = 1; tata[vecin] = nod;
}
}
}
return f[d];
}
int max_flow(int s, int d) {
int flow = 0;
while (bfs(s, d))
for (int i=0; i<L[d].size(); i++) {
int vecin = L[d][i];
if (f[vecin] && resid[vecin][d] > 0) {
int path_flow = resid[vecin][d];
while (vecin != s) {
path_flow = min(path_flow, resid[tata[vecin]][vecin]);
vecin = tata[vecin];
}
vecin = L[d][i];
resid[vecin][d] -= path_flow;
resid[d][vecin] += path_flow;
while (vecin != s) {
resid[tata[vecin]][vecin] -= path_flow;
resid[vecin][tata[vecin]] += path_flow;
vecin = tata[vecin];
}
flow += path_flow;
}
}
return flow;
}
void printEdges() {
for (int i=1; i<=n/2; i++)
for (int j=1; j<=n/2; j++)
if (i != j && resid[i][n/2+j] == 0)
fout << i << " " << j << "\n";
}
};
int main() {
int n, x, y;
fin >> n;
vector<vector<int>> L(2*n+5), resid(2*n+5, vector<int>(2*n+5));
for (int i=1; i<=n; i++) {
fin >> x >> y;
L[0].push_back(i);
L[i].push_back(0);
resid[0][i] = x;
L[n+i].push_back(2*n+1);
L[2*n+1].push_back(n+i);
resid[n+i][2*n+1] = y;
}
for (int i=1; i<=n; i++)
for (int j=1; j<=n; j++)
if (i != j) {
L[i].push_back(n+j);
L[n+j].push_back(i);
resid[i][n+j] = 1;
}
Graf g(2*n+1, L, resid);
fout << g.max_flow(0, 2*n+1) << "\n";
g.printEdges();
return 0;
}