Cod sursa(job #2469408)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 7 octombrie 2019 09:01:20
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <bitset>
#define dim 300
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
queue <int> q;
vector <int> L[dim][dim];
bitset <dim> fr;
int flux,j;
int C[dim][dim], F[dim][dim],i,p,u,minim,T[dim],n,x,y;
bool bfs(){
int nod,vecin;
fr.reset();

q.push(0);

fr[0]=1;

while(!q.empty()){

nod=q.front();
q.pop();

for(i=0;i<L[nod].size();i++){

vecin=L[nod][i];

if(!fr[vecin] && C[nod][vecin]>F[nod][vecin]){

q.push(vecin);

T[vecin]=nod;

fr[vecin]=1;

}

}

}

return fr[2*n+1];

}


int main(){
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x>>y;
		L[0].push_back(i);
		L[i].push_back(0);
		L[n+i].push_back(2*n+1);
		L[2*n+i].push_back(n+i);
		C[0][i]=x;
		C[n+i][2*n+1]=y;
	}

while (bfs()) {

for (int i=0;i<L[2*n+1].size();i++) {

p = L[2*n+1][i];

if (C[p][2*n+1] > F[p][2*n+1] && fr[p] == 1) {

minim = C[p][2*n+1] - F[p][2*n+1];

u = p;

while (u!= 0) {


minim =min(minim, C[ T[u] ][u] - F[ T[u] ][u]);



u = T[u];

}

flux += minim;

F[p][2*n+1] += minim;

F[2*n+1][p] -= minim;

u = p;

while (u != 0) {

F[ T[u] ][u] += minim;

F[ u ][ T[u] ] -= minim;

u = T[u];

}

}

}

}

fout<<flux<<"\n";

for (i=1;i<=n;i++)

for (j=n+1;j<=2*n;j++)

if (F[i][j] == 1) {

fout<<i<<" "<<j-n<<"\n";

}
}