Pagini recente » Cod sursa (job #2466141) | Cod sursa (job #596788) | Cod sursa (job #2251878) | Cod sursa (job #724033) | Cod sursa (job #1507825)
#include<fstream>
#include<vector>
#include<bitset>
#include<deque>
using namespace std;
vector <int> L[1005];
bitset<1005> u;
deque <int> q;
pair<int, int> sol[10003];
int T[1005], n, i, x, y, C[1005][1005], j, nod, ok, minim, vecin, F[1005][1005], nr, nrsol;
int bfs()
{
q.clear();
u.reset();
q.push_back(101);
u[101]=1;
ok=0;
while(!q.empty())
{
nod=*q.begin();
if(nod==102)
{
ok=1;
break;
}
for(int i=0; i<L[nod].size(); i++)
{
vecin=L[nod][i];
if(u[vecin]==0 && C[nod][vecin]-F[nod][vecin]>0)
{
q.push_back(vecin);
T[vecin]=nod;
u[vecin]=1;
}
}
q.pop_front();
}
return ok;
}
ifstream in("harta.in");
ofstream out("harta.out");
int main()
{
in>>n;
for(i=1; i<=n; i++)
{
in>>x>>y;
L[101].push_back(i);
L[i].push_back(101);
L[102].push_back(i+n);
L[i+n].push_back(102);
C[101][i]=x;
C[i+n][102]=y;
for(j=n+1; j<=2*n; j++)
{
if(j!=i+n)
{
L[i].push_back(j);
L[j].push_back(i);
C[i][j]=1;
}
}
nrsol+=x;
}
while(bfs())
{
for(i=0; i<L[102].size(); i++)
{
nod=L[102][i];
if(u[nod]==1 && C[nod][102]-F[nod][102]>0)
{
minim=C[nod][102]-F[nod][102];
for(; T[nod]!=0 && minim!=0; nod=T[nod])
{
minim=min(minim, C[T[nod]][nod]-F[T[nod]][nod]);
}
if(minim!=0)
{
nod=L[102][i];
F[nod][102]+=minim;
F[102][nod]-=minim;
for(; T[nod]!=0 && minim!=0; nod=T[nod])
{
if(T[nod]>=1 && T[nod]<=n)
{
sol[++nr].first=T[nod];
sol[nr].second=nod-n;
}
F[T[nod]][nod]+=minim;
F[nod][T[nod]]-=minim;
}
}
}
}
}
out<<nrsol<<"\n";
for(i=nr; i>=nr-nrsol+1; i--)
out<<sol[i].first<<" "<<sol[i].second<<"\n";
return 0;
}