Pagini recente » Cod sursa (job #430646) | Cod sursa (job #740623) | Cod sursa (job #26584) | Cod sursa (job #190519) | Cod sursa (job #370117)
Cod sursa(job #370117)
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 205
#define FOR(i, v) for(vector<int>::iterator i = v.begin(); i != v.end(); ++i)
#define INF 2000000000
vector <int> v[NMAX];
queue <int> q;
int F[NMAX][NMAX], C[NMAX][NMAX], viz[NMAX], T[NMAX];
int n, fin;
int min(int x,int y){
if(x>y) return y;
return x;
}
int BFS(){
memset(viz, 0, sizeof(viz));
q.push(0);
viz[0] = 1;
while(!q.empty()){
int nod = q.front();
q.pop();
if(nod == fin ) continue;
FOR(i, v[nod]){
if( viz[*i] || C[nod][*i] == F[nod][*i]) continue;
viz[*i] = 1;
T[*i] = nod;
q.push(*i);
}
}
return viz[n];
}
void construiesc_legaturi(){
int i,j;
for(i = 1; i <= n; ++i){
v[0].push_back(i);
v[i].push_back(0);
}
for(i = 1; i <= n; ++i)
for(j = n+1; j <= 2*n; ++j)
if(j-n != i) {
v[i].push_back(j);
v[j].push_back(i);
C[i][j] = 1;
}
for(i = n+1; i <= 2*n; ++i){
v[i].push_back(2*n+1);
v[2*n+1].push_back(i);
}
}
int main(){
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d",&n);
fin = 2*n + 1;
for(int i = 1; i <= n; ++i){
int x, y;
scanf("%d %d", &x, &y);
C[0][i] = x;
C[n+i][2*n+1] = y;
}
construiesc_legaturi();
while(BFS())
FOR(i, v[fin]){
if(C[*i][fin] == F[*i][fin]) continue;
int flowm = INF;
T[fin] = *i;
for(int i = fin; i != 0; i = T[i])
flowm = min( flowm, C[ T[i] ][ i ] - F[ T[i] ][ i ]);
if(flowm == 0) continue;
for(int i = fin; i != 0; i = T[i]){
F[ T[i] ][ i ] += flowm;
F[ i ][ T[i] ] -= flowm;
}
}
int c = 0;
for(int i = 1; i <= n; ++i)
for(int j = n+1; j <= 2*n; j++)
if(F[i][j]) c++;
printf("%d\n", c);
for(int i = 1; i <= n; ++i)
for(int j = n+1; j <= 2*n; j++)
if(F[i][j]) printf("%d %d\n", i, j-n);
return 0;
}