Pagini recente » Cod sursa (job #41418) | Cod sursa (job #1446773) | Cod sursa (job #2982490) | Cod sursa (job #2718967) | Cod sursa (job #387265)
Cod sursa(job #387265)
# include <fstream>
# include <iostream>
# include <cstdio>
using namespace std;
int a[203][203], n, m, in[103], out[103], t[103],fm;
void read ()
{
ifstream fin ("harta.in");
fin>>n;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j)
a[i][n+j]=1;
for (int i=1;i<=n;i++)
{
fin>>out[i]>>in[i];
a[0][i]=out[i];
a[n+i][2*n+1]=in[i];
m+=out[i];
}
}
int bfs (int s, int d)
{
int c[203], st, dr, k;
for (int i=0;i<=2*n+1;i++)
t[i]=-2;
st=dr=1;
c[st]=s;
t[s]=-1;
while (st<=dr)
{
k=c[st++];
for (int i=0;i<=2*n+1;i++)
if (a[k][i]>0 && t[i]==-2)
{
t[i]=k;
c[++dr]=i;
if (i==d)
return 1;
}
}
return 0;
}
void EK ()
{
int cmin;
while (bfs(0, 2*n+1))
{
cmin=1000000000;
for (int i=2*n+1;t[i]!=-1;i=t[i])
if (cmin>a[t[i]][i])
cmin=a[t[i]][i];
for (int i=2*n+1;t[i]!=-1;i=t[i])
{
a[t[i]][i]-=cmin;
a[i][t[i]]+=cmin;
}
fm+=cmin;
}
}
void write ()
{
freopen("harta.out", "w", stdout);
printf("%d\n", m);
for (int i=1;i<=n;i++)
for (int j=n+1;j<=2*n;j++)
if (a[i][j]==0 && i!=j-n)
printf("%d %d\n", i, j-n);
}
int main ()
{
read ();
EK();
write ();
return 0;
}