Pagini recente » Cod sursa (job #2368668) | Cod sursa (job #1543779) | Cod sursa (job #2325470) | Cod sursa (job #2829398) | Cod sursa (job #916825)
Cod sursa(job #916825)
#include <fstream>
#include <queue>
#include <cstring>
#define MAX 205
using namespace std;
int N, S, D, rez;
int C[MAX][MAX], F[MAX][MAX], dad[MAX];
bool viz[MAX];
vector<int> V[MAX];
void citire() {
ifstream in("harta.in");
in>>N;
S = 0, D = 2 * N + 1;
for(int i = 1, I, O; i <= N; i++) {
in>>I>>O;
C[S][i] = I;
C[i + N][D] = O;
V[S].push_back(i);
V[i].push_back(S);
V[i + N].push_back(D);
V[D].push_back(i + N);
for(int j = 1; j <= N; j++) {
if(i == j) continue;
V[i].push_back(j + N);
V[j + N].push_back(i);
C[i][j + N] = 1;
}
} in.close();
}
bool bfs() {
queue<int> Q;
memset(viz, 0, sizeof(viz));
memset(dad, 0, sizeof(dad));
Q.push(S); viz[S] = true;
while(!Q.empty()) {
int nod = Q.front(); Q.pop();
if(nod == D) continue;
for(size_t i = 0; i < V[nod].size(); i++) {
int dest = V[nod][i];
if(F[nod][dest] == C[nod][dest] || viz[dest]) continue;
Q.push(dest);
dad[dest] = nod;
viz[dest] = true;
}
}
return viz[D];
}
void flux() {
while(bfs()) {
for(size_t i = 0; i < V[D].size(); i++) {
int nod = V[D][i], val = 200;
if(F[nod][D] == C[nod][D] || !viz[nod]) continue;
dad[D] = nod;
nod = D;
while(nod != S) {
val = min(val, C[dad[nod]][nod] - F[dad[nod]][nod]);
nod = dad[nod];
}
if(!val) continue;
nod = D;
while(nod != S) {
F[dad[nod]][nod] += val;
F[nod][dad[nod]] -= val;
nod = dad[nod];
} rez += val;
}
}
}
void afisare() {
ofstream out("harta.out");
out<<rez<<"\n";
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
if(F[i][j + N])
out<<i<<" "<<j<<"\n";
out.close();
}
int main() {
citire();
flux();
afisare();
return 0;
}