Pagini recente » Cod sursa (job #438038) | Cod sursa (job #1024570) | Cod sursa (job #291609) | Cod sursa (job #1501520) | Cod sursa (job #2469461)
#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];
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]==0 && 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+1].push_back(n+i);
C[0][i]=x;
C[n+i][2*n+1]=y;
}
for(int i=1; i<=n; i++)
{
for(int j=n+1; j<=2*n; j++)
{
if(j-i==n)
continue;
L[i].push_back(j);
L[j].push_back(i);
C[i][j]=1;
}
}
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";
}
}