Pagini recente » Cod sursa (job #981823) | Cod sursa (job #1631021) | Cod sursa (job #3214559) | Cod sursa (job #371100) | Cod sursa (job #2205662)
#include <fstream>
#include <vector>
#include <queue>
#define Nmax 202
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int C[Nmax][Nmax],F[Nmax][Nmax];
int n,m;
vector < int > d1; //nr de drumuri care pleaca din orasul i
vector < int > d2; //nr de drumuri care intra in orasul i
void Read()
{
int i;
fin>>n;
d1.resize(n+1);
d2.resize(n+1);
for(i=1;i<=n;++i)
{
fin>>d1[i]>>d2[i];
m+=d1[i];
}
}
void Initializare()
{
int i,j;
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;++j)
if(j-i!=n)C[i][j]=1;
for(j=1;j<=n;++j)C[0][j]=d1[j];
for(j=n+1;j<=2*n;++j)C[j][2*n+1]=d2[j-n];
}
int Flux(int s)
{
queue<int>c;
vector<int>t(2*n+2);
vector<int>viz(2*n+2);
int x,i;
c.push(s); viz[s]=1;
while(!c.empty())
{
x=c.front();
c.pop();
for(i=1;i<=2*n+1;++i)
if(viz[i]==0)
{
if(F[x][i]==C[x][i])
continue;
c.push(i);
viz[i]=1;
t[i]=x;
}
}
if(viz[2*n+1]==0)return 0;
for(x=2*n+1;x!=s;x=t[x])
{
F[t[x]][x]+=1;
F[x][t[x]]-=1;
}
return 1;
}
int main()
{
Read();
Initializare();
while(true)
{
int acum = Flux(0);
if(acum == 0)
break;
}
fout<<m<<"\n";
int i,j;
for(i=1;i<=n;++i)
for(j=n+1;j<=2*n;j++)
if(F[i][j]==1) fout<<i<<" "<<j-n<<"\n";
return 0;
}