Pagini recente » Cod sursa (job #1140164) | Cod sursa (job #2964696) | Cod sursa (job #1346186) | Cod sursa (job #2674278) | Cod sursa (job #2663571)
#include <fstream>
#include <vector>
#include <deque>
#define INF 100000000
#define DIM 210
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
int n, m, c[DIM][DIM], flux[DIM][DIM], f[DIM], t[DIM], i, j, sol, in, ex;
deque <int> q;
vector <int> L[DIM];
/// flux e la inceput 0
int bfs()
{
int dim=2*n+1;
int ok=0;
f[0]=1;
for (i=1; i<=dim; i++)
f[i]=0;
q.clear();
q.push_back(0);
while (!q.empty())
{
int nod=q.front();
if (nod==dim)
ok=1;
for (i=0; i<L[nod].size(); i++)
{
int vecin=L[nod][i];
if (!f[vecin] && c[nod][vecin]>flux[nod][vecin])
{
q.push_back(vecin);
f[vecin]=1;
t[vecin]=nod;
}
}
q.pop_front();
}
return ok;
}
int main ()
{
fin>>n;
int dim=2*n+1;
for (i=1; i<=n; i++)
{
fin>>ex>>in;
sol+=ex;
L[0].push_back(i); L[i].push_back(0);
c[0][i]=ex; c[i][0]=0;
for (j=1; j<=n; j++)
{
if (j!=i)
{
L[i].push_back(n+j); L[n+j].push_back(i); c[i][n+j]=1;
}
}
L[n+i].push_back(dim); L[dim].push_back(n+i);
c[n+i][dim]=in;
}
while (bfs())
{
int minim=INF; i=dim; t[0]=-1;
while (t[i]!=-1)
{
minim=min(minim, c[t[i]][i]-flux[t[i]][i]);
i=t[i];
}
i=dim;
while (t[i]!=-1)
{
flux[t[i]][i]+=minim;
flux[i][t[i]]-=minim;
i=t[i];
}
}
fout<<sol<<"\n";
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (flux[i][n+j]==1)
fout<<i<<" "<<j<<"\n";
}