Pagini recente » Borderou de evaluare (job #1655830) | Cod sursa (job #1743350) | Borderou de evaluare (job #2405683) | Cod sursa (job #1287197) | Cod sursa (job #1052279)
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#define x first
#define y second
#define NMAX 307
#define INF 100000000
using namespace std;
int Cap[NMAX][NMAX], Flux[NMAX][NMAX], Viz[NMAX], dad[NMAX];
int n, Maxflow, m, sursa, dest;
vector <int> v[NMAX];
inline int dfs(int Nod, int dest){
if(Nod == dest)
return 1;
Viz[Nod] = 1;
for(int i = 0; i < v[Nod].size(); ++ i){
int it = v[Nod][i];
if(Viz[it] == -1 && Flux[Nod][it] != Cap[Nod][it]){
dad[it] = Nod;
int ok = dfs(it, dest);
if(ok == 1)
return 1;
}
}
return 0;
}
inline int father(int Nod, int Min){
if(Nod == sursa)
return Min;
int Dad = dad[Nod];
Min = min(Min, Cap[Dad][Nod] - Flux[Dad][Nod]);
return father(dad[Nod], Min);
}
void father2(int Nod, int Min){
if(Nod == sursa)
return;
int Dad = dad[Nod];
Flux[Nod][Dad] -= Min;
Flux[Dad][Nod] += Min;
father2(dad[Nod], Min);
}
int main(){
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d", &n);
sursa = n * 3;
dest = n * 2 + 1;
for(int i = 1; i <= n; ++i){
int a = 0, b = 0;
scanf("%d %d", &a, &b);
Cap[sursa][i] = a;
Cap[i + n][dest] = b;
v[sursa].push_back(i);
v[i].push_back(sursa);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(i != j){
Cap[i][j + n] = 1;
v[i].push_back(n + j);
v[n + j].push_back(i);
}
for(int j = 1; j <= n; ++ j){
v[dest].push_back(j + n);
v[j + n].push_back(dest);
}
memset(dad, -1, sizeof(dad));
memset(Viz, -1, sizeof(Viz));
while(dfs(sursa, dest)){
int Min = INF;
memset(Viz, -1, sizeof(Viz));
Min = father(dest, Min);
Maxflow += Min;
father2(dest, Min);
memset(dad, -1, sizeof(dad));
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(Flux[i][j + n] > 0)
++ m;
printf("%d\n", m);
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(Flux[i][j + n] > 0)
printf("%d %d\n", i, j);
return 0;
}