Pagini recente » Cod sursa (job #373354) | Cod sursa (job #2786379) | Cod sursa (job #1533483) | Cod sursa (job #2193900) | Cod sursa (job #2421573)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector <int> a[1001];
int c[1001][1001],flux[10001][1001],n,m,viz[1001],coada[1001],s,d,minim,r;
int bfs()
{
int i,prim,ultim,x,sw=0;
for(i=1;i<=d;i++)
{
viz[i]=coada[i]=0;
}
viz[s]=-1;
prim=ultim=1;
coada[prim]=s;
while(prim<=ultim)
{
x=coada[prim++];
//cout<<x<<" ";
for(i=0;i<a[x].size();i++)
{
if(viz[a[x][i]]==0 && c[x][a[x][i]]>flux[x][a[x][i]])
{
if(a[x][i]!=d)
{
viz[a[x][i]]=x;
ultim++;
coada[ultim]=a[x][i];
}
else
{
sw=1;
}
}
}
}
return sw;
}
void dinic()
{
int i,nod;
while(bfs()!=0)
{
for(i=0;i<a[d].size();i++)
{
if(viz[a[d][i]]!=0 && c[a[d][i]][d]>flux[a[d][i]][d])
{
viz[d]=a[d][i];
minim=0x7fffffff;;
nod=d;
while(nod!=s)
{
if(minim>c[viz[nod]][nod]-flux[viz[nod]][nod])
{
minim=c[viz[nod]][nod]-flux[viz[nod]][nod];
}
nod=viz[nod];
}
if(minim>0)
{
r=r+minim;
nod=d;
while(nod!=s)
{
flux[viz[nod]][nod]+=minim;
flux[nod][viz[nod]]-=minim;
nod=viz[nod];
}
}
}
}
}
}
int main()
{
int i,x,y,j;
f>>n;
s=1;
d=2*n+2;
for(i=2;i<=n+1;i++)
{
f>>x>>y;
c[s][i]=x;
c[n+i][d]=y;
a[s].push_back(i);
a[i].push_back(s);
a[n+i].push_back(d);
a[d].push_back(n+i);
}
for(i=2;i<=n+1;i++)
{
for(j=n+2;j<=2*n+1;j++)
{
if(i!=j-n)
{
c[i][j]=1;
a[i].push_back(j);
a[j].push_back(i);
}
}
}
dinic();
g<<r<<"\n";
for(i=2;i<=n+1;i++)
{
for(j=n+2;j<=2*n+1;j++)
{
if(flux[i][j]==1)
{
g<<i-1<<" "<<j-n-1<<"\n";
}
}
}
return 0;
}