Pagini recente » Monitorul de evaluare | Cod sursa (job #1330535) | Cod sursa (job #1612569) | Clasament alegem | Cod sursa (job #2961914)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,x,y,s,d,noduri,c;
vector<int>viz;
vector<int>t;//vector de muchii care duc la nodurile respective
vector<vector<int>>indici; //vector de indici de muchii;
// indici[i] = vector de muchii care ies din i
vector<int>out;
vector<int>in;
struct muchie{
int x,y,c,poz;
};
vector<muchie>M;
int BFS(){
t.clear();
t.resize(n);
fill(viz.begin(), viz.end(), 0);
queue<int>q;
viz[s]=1;
q.push(s);
while(!q.empty()){
int vf = q.front();
q.pop();
for(auto aux:indici[vf]){
muchie mc = M[aux];
if(!viz[mc.y] && mc.c>0){
q.push(mc.y);
viz[mc.y] = 1;
t[mc.y] = aux;
if(mc.y == d){
return 1;
}
}
}
}
return 0;
}
int main() {
f>>n;
noduri = n*2 + 2;
s = 0;
d = noduri-1;
viz.resize(noduri);
t.resize(noduri);
indici.resize(noduri);
in.resize(n+1);
out.resize(n+1);
for(int i=1;i<=n;i++){
f>>x>>y;
out[i]=x;//nr drumuri care ies din i
in[i]=y;//nr drumuri care intra in i
}
int dim = 0;
//creez drumurile posibile
for(int i=1;i<=n;i++){
for(int j=1+n;j<=n*2;j++){
if(i!=j-n){//verific sa nu am drum de la i la i
dim+=2;
M.push_back({i,j,1,dim-1});
M.push_back({j,i,0,dim-2});
indici[i].push_back(dim-2);
indici[j].push_back(dim-1);
}
}
}
//adaug drumuri de la o sursa 0 la fiecare oras
//drumurile de la s la i au flux=dr care ies din i
for(int i=1;i<=n;i++){
dim+=2;
M.push_back({s,i,out[i],dim-1});
M.push_back({i,s,0,dim-2});
indici[s].push_back(dim-2);
indici[i].push_back(dim-1);
}
//adaug drumuri de la fiecare oras la o destinatie d
//dr de la i la d au flux=dr care intra in i
for(int i = 1+n; i<=n*2; i++){
dim+=2;
M.push_back({i,d,in[i-n],dim-1});
M.push_back({d,i,0,dim-2});
indici[i].push_back(dim-2);
indici[d].push_back(dim-1);
}
c=0;
while(BFS()){
for(auto aux:indici[d]){//verific mai multe drumuri
if(viz[M[aux].y] && M[M[aux].poz].c!=0){//M[aux].y=tatal lui d
//M[M[aux].poz]=muchie care iese din tatal lui d
int minim = INT_MAX;
muchie mc = M[aux];
t[d] = mc.poz;
int nod = d;
while(nod != s){
minim = min(minim, M[t[nod]].c);
nod = M[t[nod]].x;
}
c +=minim;
nod = d;
while(nod!=s){
M[t[nod]].c -= minim;
M[M[t[nod]].poz].c +=minim;
nod = M[t[nod]].x;
}
}
}
}
g<<c<<"\n";
for(auto aux: M){
if(aux.c==0 && aux.x!=s && aux.y!=d && aux.x<aux.y){
g<<aux.x << " " << aux.y-n<<"\n";
}
}
return 0;
}