Pagini recente » Cod sursa (job #915108) | Cod sursa (job #717651) | Cod sursa (job #1192622) | Cod sursa (job #576682) | Cod sursa (job #585241)
Cod sursa(job #585241)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define INF 32000
int N;
int GREX[100];
int GRIN[100];
int SRC;
int DEST;
short MATAD[202][202];
short FLUX[202][202];
typedef struct _QElem {
int node, level;
short cap;
struct _QElem* parent;
} QElem;
static void initMatad() {
memset(MATAD, 0, 202*202*sizeof(short));
for (int i=0; i<2*N+2; i++) {
for (int j=0; j<2*N+2; j++) {
if ((i == SRC) && (j < N)) {
MATAD[i][j] = GREX[j];
} else if ((i >= N) && (i < 2*N) && (j == DEST)) {
MATAD[i][j] = GRIN[i-N];
} else if ((i < N) && (j >= N) && (j < 2*N) && (i != j-N)) {
MATAD[i][j] = 1;
}
}
}
}
static void initFlux() {
memset(FLUX, 0, 202*202*sizeof(short));
}
static void push(int a, int b, short amount) {
FLUX[a][b] += amount;
FLUX[b][a] -= amount;
MATAD[a][b] -= amount;
MATAD[b][a] += amount;
}
static void fluxMax() {
static QElem queue[202];
static int visited[202];
int start;
int end;
QElem* dest;
while (1) {
start = 0;
end = 0;
dest = NULL;
memset(visited, 0, sizeof(int)*202);
queue[end].node = SRC;
queue[end].level = 0;
queue[end].cap = INF;
queue[end].parent = NULL;
end++;
while (start < end) {
int nodC = queue[start].node;
for (int i=0; i<2*N+2; i++) {
if ((MATAD[nodC][i] > 0) && !visited[i]) {
visited[i] = 1;
queue[end].node = i;
if (i == DEST) dest = queue+end;
queue[end].parent = queue+start;
queue[end].level = queue[start].level+1;
queue[end].cap = min(queue[start].cap, MATAD[nodC][i]);
end++;
}
}
start++;
}
if (!dest) return;
short destCap = dest->cap;
while (dest->parent != NULL) {
push(dest->parent->node, dest->node, destCap);
dest = dest->parent;
}
}
}
int main(int argc, char** argv) {
ifstream fisIn("harta.in");
ofstream fisOut("harta.out");
fisIn >> N;
for (int i=0; i<N; i++) {
fisIn >> GREX[i] >> GRIN[i];
}
SRC = 2*N;
DEST = 2*N+1;
initMatad();
initFlux();
fluxMax();
int count = 0;
for (int i=0; i<2*N; i++) {
for (int j=0; j<2*N; j++) {
if (FLUX[i][j] > 0) count++;
}
}
fisOut << count << "\n";
for (int i=0; i<2*N; i++) {
for (int j=0; j<2*N; j++) {
if (FLUX[i][j] > 0)
fisOut << (i+1) << " " << (j-N+1) << "\n";
}
}
fisOut.close();
return 0;
}