Pagini recente » Cod sursa (job #3159457) | Borderou de evaluare (job #1010228) | Cod sursa (job #2503242) | Cod sursa (job #765198) | Cod sursa (job #2961610)
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream o("harta.out");
int n, s, d, mmm;
int cap[201][201], flux[201][201], p[201];
vector <int> G[201];
vector <pair <int, int>> ans;
bool path[201];
bool bfs() {
memset(path, 0, sizeof path);
queue <int> q;
q.push(s);
while(!q.empty()) {
int poz = q.front();
q.pop();
if(poz == d) continue;
for(auto vecin : G[poz]) {
if(!path[vecin] && cap[poz][vecin] > flux[poz][vecin]) {
path[vecin] = 1;
p[vecin] = poz;
q.push(vecin);
}
}
}
}
int main() {
f>>n;
s = 0;
d = 2 * n + 1;
for(int i = 1; i <= n; i++) {
int x, y;
f>>x>>y;
cap[s][i] = x;
cap[n + i][d] = y;
}
for(int i = 1; i <= n; i++) {
G[s].push_back(i);
G[i].push_back(s);
G[d].push_back(n + i);
G[n + i].push_back(d);
for(int j = 1; j <= n; j++) {
if(j != i) {
G[i].push_back(j + n);
G[j + n].push_back(i);
cap[i][j + n] = 1;
}
}
}
while(bfs()) {
for(int x = d; x != s; x = p[x]) {
flux[p[x]][x]++;
flux[x][p[x]]--;
}
mmm++;
}
o<<mmm<<'\n';
for(int i = 1; i <= n; i++) for(int j = n + 1; j <= 2 * n; j++) if(flux[i][j]) o<<i<<' '<<j - n<<'\n';
return 0;
}