Pagini recente » Cod sursa (job #675147) | Cod sursa (job #1759383) | Cod sursa (job #1194748) | Cod sursa (job #118455) | Cod sursa (job #887411)
Cod sursa(job #887411)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define nmax 105*2
#define ll long long
#define inf (1<<30)
int n, intra[nmax/2], iese[nmax/2], capac[nmax][nmax], flux[nmax][nmax], t[nmax];
bool viz[nmax];
vector<int> gf[nmax];
int Cnt = 0;
int q[nmax*2];
void citeste(){
f >> n;
for(int i=1; i<=n; ++i){
f >> intra[i] >> iese[i];
Cnt += intra[i];
}
}
void bagaS(int S){
// muchii de genul S - > i de capacitate iese[i]
for(int i=1; i<=n; ++i){
if (iese[i] == 0) continue;
gf[S].push_back(i);
gf[i].push_back(S);
capac[S][i] = iese[i];
}
}
void bagaD(int D){
// muchii de genul i -> D de capacitate intra[i]
for(int i=1; i<=n; ++i){
if (intra[i] == 0) continue;
int i2 = i + n;
gf[i2].push_back(D);
gf[D].push_back(i2);
capac[i2][D] = intra[i];
}
}
void faGraf(){
// pe alea din multimea dreapta le reindexez de la n+1 la n*2;
for(int i=1; i<=n; ++i){
if (iese[i] == 0) continue;
for(int j=1; j<=n; ++j){
if (i == j || intra[j] == 0) continue;
int j2 = n+j;
gf[i].push_back(j2);
gf[j2].push_back(i);
capac[i][j2] = 1;
}
}
int S = 0; int D = n*2+1;
bagaS(S); bagaD(D);
}
inline bool bfs(int S, int D){
for(int i=0; i<=D; ++i) viz[i] = 0, t[i] = 0;
int st=1; int dr=0;
q[++dr] = S; viz[S] = 1;// e marcat
for(; st<=dr; ){
int nod = q[st]; ++st;
for(int i=0; i<gf[nod].size(); ++i){
int vc = gf[nod][i];
if (viz[vc] == 0 && capac[nod][vc] > flux[nod][vc]){
t[vc] = nod;
viz[vc] = 1;
q[++dr] = vc;
}
}
}
return viz[D];
}
void rezolva(){
// ideea ar fi asa imi formez un graf bipartiti in care intr-o parte am nodurile semnificand nr de muchii ce ies din nod
// iar in cealalta cele care intra; pot baga un cuplaj maxim; pt a scapa de restrictiile din enunt il fac cu flux
// astfel mai bag o sursa si o destinatie; bag cate o muchie de la sursa la fiecare nod din multimea stanga
// doar ca pun capacitatea egala cu muchiile care ies din fiecare nod
// iar apoi din fiecaren od din multimea dreapta bag o muchie in destinatie cu capacitatea egala cu nr de muchiii ce intra in fiecare nod
// astfel facand un flux maxim pe graful format imi va da graful cerut
// iar intre nodurile din multimi bag cate o muchie de capacitate 1;
faGraf();
// air acum pe graful asta bag un flux maxim
int S = 0; int D = 2*n+1;
for(; bfs(S, D); ){
int Min = inf;
for(int i=D; i!=S; i=t[i]){
// am muchie de genul t[i]->i
Min = min(Min, capac[ t[i] ][i] - flux[ t[i] ][i]);
}
//bag fluxul
for(int i=D; i!=S; i=t[i]){
flux[ t[i] ][i] += Min;
flux[i][ t[i] ] -= Min;
}
}
// muchiile noului graf vor fi acele muchii din graful rezidual care sunt saturate
//cout << Cnt << "\n";
g << Cnt << "\n";
for(int i=1; i<=n; ++i){
for(int j=n+1; j<=2*n; ++j){
if (flux[i][j] != 0){
//cout << j-n << " " << i << "\n";
g << j-n << " " << i << "\n";
}
}
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}