Pagini recente » Cod sursa (job #3002094) | Cod sursa (job #2397193) | Cod sursa (job #576458) | Cod sursa (job #2097735) | Cod sursa (job #2661342)
#include <fstream>
#include <bitset>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,i,cap[DIM][DIM],flux[DIM][DIM],t[DIM],fmin,fsol,nod,vecin,x,y,j;
bitset<DIM> f;
vector<int> L[DIM];
deque<int> q;
int bfs() {
f.reset();
f[0]=1;
q.push_back(0);
while (!q.empty()) {
nod=q.front();
for (int i=0;i<L[nod].size();i++) {
int vecin=L[nod][i];
if (f[vecin]==0&&cap[nod][vecin]>flux[nod][vecin]) {
f[vecin]=1;
q.push_back(vecin);
t[vecin]=nod;
}
}
q.pop_front();
}
return f[2*n+1];
}
int main() {
fin>>n;
for (i=1;i<=n;i++) { //copiem nodurile grafului in 2 liste identice
fin>>x>>y; //si pe muchia dintre sursa si lista din stanga
cap[0][i]=x; //sau dintre destinatie si lista din dreapta
L[0].push_back(i);//punem capacitatea egala cu cate drumuri ies/intra in oras
L[i].push_back(0);
cap[n+i][2*n+1]=y;
L[n+i].push_back(2*n+1);
L[2*n+1].push_back(n+i);
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i!=j) {
cap[i][n+j]=1; //ducem muchie de la fiecare nod din lista stanga
L[i].push_back(n+j);//la celelalte din lista dreapta in afara de el
L[n+j].push_back(i);
}
while (bfs()) {
for (i=0;i<L[2*n+1].size();i++) {
vecin=L[2*n+1][i];
if (cap[vecin][2*n+1]-flux[vecin][2*n+1]>0&&f[vecin]==1) {
fmin=cap[vecin][2*n+1]-flux[vecin][2*n+1];
nod=vecin;
while (nod!=0) {
fmin=min(fmin,cap[t[nod]][nod]-flux[t[nod]][nod]);
nod=t[nod];
}
fsol+=fmin;
flux[vecin][2*n+1]+=fmin;
flux[2*n+1][vecin]-=fmin;
nod=vecin;
while (nod!=0) {
flux[t[nod]][nod]+=fmin;
flux[nod][t[nod]]-=fmin;
nod=t[nod];
}
}
}
}
fout<<fsol<<"\n";
for (i=1;i<=n;i++)
for (j=n+1;j<=2*n;j++)
if (flux[i][j]==1)
fout<<i<<" "<<j-n<<"\n";
return 0;
}