Pagini recente » Cod sursa (job #690236) | Cod sursa (job #321093) | Cod sursa (job #982019) | Cod sursa (job #2586458) | Cod sursa (job #420459)
Cod sursa(job #420459)
#include<fstream>
#include<cstdio>
#include<vector>
using namespace std;
#define D 2*n+1
#define S 0
#define DIM 202
#define INFI 2000000000
#define pb push_back
int cap[DIM][DIM], t[DIM], n, fluxmax;
void citire()
{
int i, j;
ifstream fin("harta.in");
fin>>n;
for(i=1;i<=n; i++)
for(j=1;j<=n;j++)
if(i!=j)
cap[i][j+n]=1;
for(i=1;i<=n;i++)
{
int ies, intra;
fin>>ies>>intra;
cap[S][i]=ies;
cap[i+n][D]=intra;
}
}
int bfs(int start, int end)
{
vector<int> coada;
int st, dr, k, i;
st=dr=0;
coada.pb(start);
for(i=0;i<=D;i++)
t[i]=-2;
t[start]=-1;
while(st<=dr)
{
k=coada[st++];
for(i=0; i<=D;++i)
if(t[i]==-2 && cap[k][i])
{
t[i]=k;
if(i==D)
{
coada.clear();
return 1;
}
coada.pb(i);
dr++;
}
}
coada.clear();
return 0;
}
void e_k()
{
int cmin,k;
while(bfs(S,D))
{
cmin=INFI;
for(k=D; t[k]!=-1 ; k=t[k])
if(cap[t[k]][k]<cmin)
cmin=cap[t[k]][k];
fluxmax+=cmin;
for(k=D; t[k]!=-1 ; k=t[k])
{
cap[t[k]][k]-=cmin;
cap[k][t[k]]+=cmin;
}
}
}
void afis()
{
int i,j;
printf("%d\n",fluxmax);
for(i=1;i<=n;i++)
for(j=n+1;j<D;j++)
if(i!=j-n && cap[i][j]==0)
printf("%d %d\n", i, j-n);
}
int main()
{
freopen("harta.out","w",stdout);
citire();
e_k();
afis();
return 0;
}