Pagini recente » Cod sursa (job #1315322) | Cod sursa (job #1307581) | Cod sursa (job #2377120) | Cod sursa (job #64214) | Cod sursa (job #3193367)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
int N,M,k,x,parinte[202],dist,cap[202][202],flux[202][202],in,out;
bool viz[202];
ifstream fin ("harta.in");
ofstream fout ("harta.out");
void bfs()
{
for(int i=1; i<=2*N+1 ;i++)
{
parinte[i]=-1;
viz[i]=false;
}
queue <int> q;
q.push(0);
viz[0]=true;
parinte[0]=-1;
while(!q.empty())
{
int x=q.front();
q.pop();
if(x != dist)
{
if(x >= 1 && x <= N)
{
for(int i=N+1; i<=2*N; i++)
if(!viz[i] && cap[x][i] != flux[x][i])
{
viz[i]=true;
parinte[i]=x;
q.push(i);
}
}
else
{
for(int i=1;i<=N;i++)
if(!viz[i] && cap[x][i] != flux[x][i])
{
viz[i]=true;
parinte[i]=x;
q.push(i);
}
if(x != 0 && !viz[dist] && cap[x][dist] != flux[x][dist])
{
viz[dist]=true;
parinte[dist]=x;
q.push(dist);
}
}
}
}
}
int maxim()
{
int flux_max=0;
bfs();
while(viz[dist])
{
for(int i=N+1;i<=2*N;i++)
{
if(viz[i] && cap[i][dist] != flux[i][dist])
{
parinte[dist]=i;
int flux_min=100000,poz=dist;
while(poz)
{
flux_min=min(flux_min, cap[parinte[poz]][poz] - flux[parinte[poz]][poz]);
poz=parinte[poz];
}
if(flux_min != 0)
{
flux_max+=flux_min;
poz=dist;
while(poz)
{
flux[parinte[poz]][poz]+=flux_min;
flux[poz][parinte[poz]]-=flux_min;
poz=parinte[poz];
}
}
}
}
bfs();
}
return flux_max;
}
int main()
{
fin >> N;
dist= 2 * N + 1;
for(int i=1;i<=N;i++)
{
fin >> out >> in;
M+=out;
cap[0][i]=out;
cap[i+N][dist]=in;
}
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
if(j!=i)
cap[i][j+N]=1;
fout << maxim() << '\n';
for(int i=1;i<=N;i++)
for(int j=N+1;j<=2*N;j++)
if(flux[i][j])
fout << i << ' ' << j - N << '\n';
fin.close();
fout.close();
return 0;
}