Pagini recente » Cod sursa (job #473083) | Cod sursa (job #893873) | Cod sursa (job #1758783) | Cod sursa (job #582064) | Cod sursa (job #2701156)
#include <bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
vector <int> v[305];
int n,tata[205],c[205][205],flux[205][205],lim,i,x,y,j,nod,sol,solutie;
bool exista_drum(int inceput)
{
queue <int> q;
int i;
for (i=0;i<=lim;i++)
{
tata[i]=-1;
}
tata[inceput]=0;
q.push(inceput);
while (!q.empty())
{
int curent=q.front();
q.pop();
for (int j=0;j<v[curent].size();j++)
{
int nod=v[curent][j];
if (tata[nod]==-1&&c[curent][nod]>flux[curent][nod])
{
tata[nod]=curent;
q.push(nod);
if (nod==lim)
{
return 1;
}
}
}
}
return 0;
}
int main()
{
in>>n;
lim=2*n+1;
for (i=1;i<=n;i++)
{
in>>x>>y;
v[0].push_back(i);
v[i].push_back(0);
c[0][i]=x;
v[n+i].push_back(lim);
v[lim].push_back(n+i);
c[n+i][lim]=y;
}
for (i=1;i<=n;i++)
{
for (j=n+1;j<=lim-1;j++)
{
if (j-i!=n)
{
v[i].push_back(j);
v[j].push_back(i);
c[i][j]=1;
}
}
}
while (exista_drum(0)==1)
{
for (j=0;j<v[lim].size();j++)
{
nod=v[lim][j];
if (tata[nod]==-1)
{
continue;
}
sol=c[nod][lim]-flux[nod][lim];
while (nod!=0)
{
sol=min(sol,c[tata[nod]][nod]-flux[tata[nod]][nod]);
nod=tata[nod];
}
solutie+=sol;
nod=v[lim][j];
flux[nod][lim]+=sol;
flux[lim][nod]-=sol;
while (nod!=0)
{
flux[tata[nod]][nod]+=sol;
flux[nod][tata[nod]]-=sol;
nod=tata[nod];
}
}
}
out<<solutie<<'\n';
for (i=1;i<=n;i++)
{
for (j=n+1;j<=lim-1;j++)
{
if (j-i!=n&&flux[i][j]==1)
{
out<<i<<" "<<j-n<<'\n';
}
}
}
return 0;
}