Pagini recente » Cod sursa (job #1301422) | Cod sursa (job #519661) | Cod sursa (job #2718671) | Cod sursa (job #1005751) | Cod sursa (job #544735)
Cod sursa(job #544735)
#include <stdio.h>
#include <vector>
using namespace std;
int c[256][256],f[256][256],v[256],q[256],p[256],n,s;
vector <int> g[256];
int bfs()
{
int i,j,a,b;
for (i=2;i<=n;++i) v[i]=0;
v[1]=1;q[0]=1;q[1]=1;
for (i=1;i<=q[0];++i)
{
a=q[i];
if (a!=n)
for (j=0;j<g[a].size();++j)
{
b=g[a][j];
if ((c[a][b]>f[a][b])&&(!v[b]))
{
++q[0];
q[q[0]]=b;
p[b]=a;
v[b]=1;
}
}
}
return v[n];
}
int main()
{
int i,j,x,y,a,t;
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;++i)
{
scanf("%d%d",&x,&y);
g[1].push_back(i+1);
g[i+1].push_back(1);
g[n+i+1].push_back(2*n+2);
g[2*n+2].push_back(n+i+1);
c[1][i+1]=x;
c[n+i+1][2*n+2]=y;
s+=x;
}
for (i=1;i<=n;++i)
for (j=1;j<=n;++j)
if (i!=j)
{
g[i+1].push_back(n+j+1);
g[n+j+1].push_back(i+1);
c[i+1][n+j+1]=1;
}
n=2*n+2;
while (bfs())
for (i=0;i<g[n].size();++i)
{
a=g[n][i];
if ((c[a][n]>f[a][n])&&v[a])
{
p[n]=a;
t=10000;
for (a=n;a!=1;a=p[a])
t=min(t,c[p[a]][a]-f[p[a]][a]);
for (a=n;a!=1;a=p[a])
{
f[p[a]][a]+=t;
f[a][p[a]]-=t;
}
}
}
printf("%d\n",s);
for (i=1;i<=n/2;++i)
for (j=1;j<=n/2;++j)
if ((j!=i)&&f[i+1][j+n/2])
printf("%d %d\n",i,j);
return 0;
}