Pagini recente » Cod sursa (job #2932613) | Cod sursa (job #2933045) | Cod sursa (job #1573906) | Cod sursa (job #2954467)
#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <string.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
const int NMAX = 2*1e3 + 10;
int n, m, cap[NMAX][NMAX], seen[NMAX], f[NMAX][NMAX], father[NMAX];
vector<int> g[NMAX];
int bf() {
queue<int> q;
memset(seen, 0, sizeof(seen));
q.push(0);
seen[0] = 1;
while (!q.empty()) {
int node = q.front();
q.pop();
if (node == 2*n+1)
continue;
for (int next: g[node]) {
if (cap[node][next] == f[node][next] || seen[next])
continue;
father[next]=node;
seen[next] = 1;
q.push(next);
}
}
return seen[2*n+1];
}
int main() {
in >> n;
for (int i = 1, a, b; i <= n; i++) {
in >> a >> b;
g[0].push_back(i);
g[i].push_back(0);
cap[0][i]=a;
g[n+i].push_back(2*n+1);
g[2*n+1].push_back(n+i);
cap[n+i][2*n+1]=b;
}
for(int i=1;i<=n;i++)
for(int j=n+1 ; j<=2*n;j++){
if(i+n!=j){
g[i].push_back(j);
g[j].push_back(i);
cap[i][j]=1;
}
}
int flow = 0;
while (bf())
for (int node: g[2*n+1]) {
int fmin = 2e9;
if (f[node][2*n+1] == cap[node][2*n+1] || !seen[node])
continue;
father[2*n+1] = node;
for (node = 2*n+1; node != 0; node = father[node]) {
fmin = min(fmin, cap[father[node]][node] - f[father[node]][node]);
}
if (fmin == 0)
continue;
for (node = 2*n+1; node != 0; node = father[node]) {
f[father[node]][node] += fmin;
f[node][father[node]] -= fmin;
}
flow += fmin;
}
out << flow<<'\n';
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(i+n!=j && f[i][j]==1)
out<<i<<" "<<j-n<<'\n';
return 0;
}