Pagini recente » Cod sursa (job #1931030) | Cod sursa (job #945296) | Cod sursa (job #1159954) | Cod sursa (job #953565) | Cod sursa (job #2661492)
#include <cstdio>
#include <vector>
#define DIM 210
#define INF 2000000000
using namespace std;
int s,d;
int f[DIM],dq[DIM],a[DIM][DIM],fl[DIM][DIM],ok,tt[DIM],vf[DIM];
vector <int> v[DIM];
int bfs (int s){
int i,p,u,nod,vecin;
for (i=s;i<=d;i++)
f[i]=0;
ok=0;
p=u=1;
dq[p]=s;
f[s]=1;
while (p<=u){
nod=dq[p];
for (i=0;i<v[nod].size();i++){
vecin=v[nod][i];
if (f[vecin]==0 && fl[nod][vecin]<a[nod][vecin]){
f[vecin]=1;
dq[++u]=vecin;
tt[vecin]=nod;
}
if (vecin==d && fl[nod][vecin]<a[nod][vecin])
vf[++ok]=nod;
}
p++;
}
return f[d];
}
int main()
{
FILE *fin=fopen ("harta.in","r");
FILE *fout=fopen ("harta.out","w");
int n,i,x,y,j,nod,vecin,mini,flux;
fscanf (fin,"%d",&n);
s=0;
d=2*n+1;
for (i=1;i<=n;i++){
fscanf (fin,"%d%d",&x,&y);
v[s].push_back(i);
v[i].push_back(s);
a[s][i]=x;
v[i+n].push_back(d);
v[d].push_back(i+n);
a[i+n][d]=y;
}
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
if (i!=j){
v[i].push_back(j+n);
v[j+n].push_back(i);
a[i][j+n]=1;
}
}
tt[s]=-1;
while (bfs(s)){
for (i=1;i<=ok;i++){
nod=vf[i]; // nod sunt vecinii destinatiei in care am ajuns
vecin=d;
mini=INF;
while (nod!=-1){
//printf ("%d ",nod);
mini=min(mini,a[nod][vecin]-fl[nod][vecin]);
vecin=nod;
nod=tt[nod];
}
//printf ("\n");
nod=vf[i];
vecin=d;
while (nod!=-1){
fl[nod][vecin]+=mini;
fl[vecin][nod]-=mini;
vecin=nod;
nod=tt[nod];
}
}
}
flux=0;
for (i=1;i<=n;i++)
flux+=fl[s][i];
fprintf (fout,"%d\n",flux);
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (i!=j && fl[i][j+n])
fprintf (fout,"%d %d\n",i,j);
return 0;
}