Pagini recente » Cod sursa (job #95941) | Cod sursa (job #948843) | Cod sursa (job #2801795) | Cod sursa (job #96495) | Cod sursa (job #3329904)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct Muchie {
int v, cap, flux, rev;
};
vector<Muchie> G[300];
int tata[300];
int id[300];
int N, S, D;
void add(int x, int y, int cap) {
Muchie a = {y, cap, 0, (int)G[y].size()};
Muchie b = {x, 0, 0, (int)G[x].size()};
G[x].push_back(a);
G[y].push_back(b);
}
bool bfs() {
fill(tata, tata + D + 1, -1);
queue<int> Q;
Q.push(S);
tata[S] = -2;
while(!Q.empty()){
int nod = Q.front();
Q.pop();
for(int i = 0; i < G[nod].size(); i++){
Muchie &m = G[nod][i];
if(tata[m.v] == -1 && m.cap - m.flux > 0){
tata[m.v] = nod;
id[m.v] = i;
Q.push(m.v);
if(m.v == D) return true;
}
}
}
return false;
}
int main() {
fin >> N;
S = 0;
D = 2 * N + 1;
int total_drumuri = 0;
for(int i = 1; i <= N; i++) {
int out, in;
fin >> out >> in;
add(S, i, out);
add(N + i, D, in);
total_drumuri += out;
}
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= N; j++) {
if(i != j) {
add(i, N + j, 1);
}
}
}
while(bfs()) {
int nod = D;
while(nod != S) {
int prev = tata[nod];
int idx = id[nod];
G[prev][idx].flux++;
int rev = G[prev][idx].rev;
G[nod][rev].flux--;
nod = prev;
}
}
fout << total_drumuri << "\n";
for(int i = 1; i <= N; i++) {
for(int k = 0; k < G[i].size(); k++) {
if(G[i][k].v > N && G[i][k].v <= 2 * N && G[i][k].flux == 1) {
fout << i << " " << G[i][k].v - N << "\n";
}
}
}
return 0;
}