Pagini recente » Cod sursa (job #76380) | Cod sursa (job #62107) | Cod sursa (job #1603701) | Cod sursa (job #399755) | Cod sursa (job #3189534)
#include <bits/stdc++.h>
using namespace std;
const int N = 2e2 + 10, INF = INT_MAX;
int cap[N][N], n, S = 0, D, rez[N][N], val_rez;
vector <int> adc[N];
bool bfs(int src, int dst, vector<int> &parent, bitset<N> &viz){
fill(parent.begin(), parent.end(), 0);
viz.reset();
queue <int> q;
// bitset <N> viz;
viz[src] = true;
q.push(src);
while(!q.empty()){
int nact = q.front();
q.pop();
if(nact == dst)
continue;
for(auto adiacent: adc[nact]){
if(rez[nact][adiacent] == cap[nact][adiacent] || viz[adiacent])
continue;
q.push(adiacent);
parent[adiacent] = nact;
viz[adiacent] = true;
}
}
// cout << "BFS " << viz[dst] << "\n";
return viz[dst];
}
void max_flux(int src, int dst){
vector <int> parent(dst + 10);
bitset <N> viz;
while(bfs(src, dst, parent, viz)){
for(auto adiacent: adc[dst]){
if(rez[adiacent][dst] == cap[adiacent][dst] || !viz[adiacent])
continue;
// cout << adiacent << "\n";
parent[dst] = adiacent;
int aux = dst, val = N;
while(aux != src){
// int tata = parent[aux];
val = min(val, cap[parent[aux]][aux] - rez[parent[aux]][aux]);
aux = parent[aux];
}
if(!val)
continue;
aux = dst;
while(aux != src){
// cout << aux << " ";
// int tata = parent[aux];
rez[parent[aux]][aux] += val;
rez[aux][parent[aux]] -= val;
aux = parent[aux];
}
// cout << "\n";
val_rez += val;
}
}
}
int main() {
ifstream f("harta.in");
ofstream g("harta.out");
f >> n;
D = 2 * n + 1;
for(int i = 1; i <= n; i++) {
int a, b;
f >> a >> b;
cap[S][i] = a;
cap[n + i][D] = b;
adc[S].push_back(i);
adc[i].push_back(S);
adc[n + i].push_back(D);
adc[D].push_back(n + i);
for (int j = 1; j <= n; j++) {
if (i == j)
continue;
adc[i].push_back(j + n);
adc[j + n].push_back(i);
cap[i][j + n] = 1;
}
}
max_flux(S, D);
g << val_rez << "\n";
for(int i = 1; i <= n; i++){
for(int j = 1; j <= n; j++){
if(rez[i][j + n]){
g << i << " " << j << "\n";
}
}
}
g.close();
f.close();
return 0;
}