Pagini recente » Cod sursa (job #347202) | Cod sursa (job #3269775) | Cod sursa (job #854011) | Cod sursa (job #1157954) | Cod sursa (job #428373)
Cod sursa(job #428373)
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define N_Max 101
#define INF 999999999
int N, C[205][205], F[205][205], TT[205], viz[205];
vector<int> G[205];
struct IO {
int in, out;
} O[N_Max];
int BFS() {
//BFS de la 1 la 2*N+2
queue<int> Q;
memset(viz, 0, sizeof(viz));
memset(TT, 0, sizeof(TT));
int p;
viz[1]=1; Q.push(1);
while(!Q.empty()) {
p=Q.front(); Q.pop();
for(vector<int>::iterator it=G[p].begin(); it!=G[p].end(); it++) {
if(!viz[(*it)] && C[p][(*it)]>F[p][(*it)]) {
viz[(*it)]=1;
Q.push((*it));
TT[(*it)]=p;
if((*it)==2*N+2) { return 1; }
}
}
}
return 0;
}
int main() {
FILE *f1=fopen("harta.in", "r"), *f2=fopen("harta.out", "w");
int i, j, p, q, c;
fscanf(f1, "%d\n", &N);
for(i=1; i<=N; i++) {
fscanf(f1, "%d %d\n", &O[i].out, &O[i].in);
}
for(i=2; i<=N+1; i++) {
for(j=N+2; j<=2*N+1; j++) {
if(i-1!=j-N-1) {
G[i].push_back(j);
G[j].push_back(i);
C[i][j]=1;
}
}
}
for(i=2; i<=N+1; i++) {
G[1].push_back(i);
G[i].push_back(1);
C[1][i]=O[i-1].out;
}
for(i=N+2; i<=2*N+1; i++) {
G[i].push_back(2*N+2);
G[2*N+2].push_back(i);
C[i][2*N+2]=O[i-N-1].in;
}
while(BFS()) {
int fmin=INF;
for(i=2*N+2; i!=1; i=TT[i]) {
fmin=min(fmin, C[TT[i]][i]-F[TT[i]][i]);
}
for(i=2*N+2; i!=1; i=TT[i]) {
F[TT[i]][i]+=fmin;
F[i][TT[i]]-=fmin;
}
}
int sol=0;
for(i=2; i<=N+1; i++) {
for(j=N+2; j<=2*N+1; j++) {
if(F[i][j]) sol++;
}
}
fprintf(f2, "%d\n", sol);
for(i=2; i<=N+1; i++) {
for(j=N+2; j<=2*N+1; j++) {
if(F[i][j]) fprintf(f2, "%d %d\n", i-1, j-N-1);
}
}
fclose(f1); fclose(f2);
return 0;
}