Pagini recente » Cod sursa (job #665971) | Cod sursa (job #1469084) | Cod sursa (job #1312646) | Cod sursa (job #1406761) | Cod sursa (job #1442268)
#include <iostream>
#include<vector>
#include<fstream>
#include<queue>
#define MAXN 210
using namespace std;
vector<int> L[MAXN];
int F[MAXN][MAXN],C[MAXN][MAXN],tata[MAXN],flux;
int sursa,dest,n,m;
queue<int> Q;
void initializare()
{
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i!=j)
{
L[i].push_back(j+n);
L[j+n].push_back(i);
C[i][j+n]=1;
}
}
}
sursa=2*n + 1;
dest=2*n + 2;
}
void citire()
{
int x,y;
ifstream fin("harta.in");
fin>>n;
initializare();
for(int i=1;i<=n;++i)
{
fin>>x>>y;
L[sursa].push_back(i);
L[i].push_back(sursa);
C[sursa][i]=x;
L[i+n].push_back(dest);
L[dest].push_back(i+n);
C[i+n][dest]=y;
}
fin.close();
// for(int i=0;i<L[sursa].size();++i)
// cout<<L[sursa][i]<<" ";
}
void reset()
{
for(int i=1;i<=dest;++i)
tata[i]=-1;
tata[sursa]=0;
}
int BFS()
{
reset();
Q.push(sursa);
while(!Q.empty())
{
int nod=Q.front();
Q.pop();
for(int i=0;i<L[nod].size();++i)
{
int k=L[nod][i];
if(tata[k]==-1 && F[nod][k] < C[nod][k])
{
Q.push(k);
tata[k]=nod;
}
}
}
if(tata[dest]==-1)
return 0;
return 1;
}
void fluxMaxim()
{
while(BFS())
{
//parcurg vecinitii nodului destinatie
for(int i=0;i<L[dest].size();++i)
{
int k=L[dest][i];
if(F[k][dest] < C[k][dest])
{
int cost = C[k][dest] - F[k][dest];
//calculez fluxul de pe acest drum
while(tata[k]!=0)
{
int t=tata[k];
cost= min(cost, C[t][k] - F[t][k]);
k=t;
}
flux+=cost;
k=L[dest][i];
//actualizez fluxul
F[dest][k]-=cost;
F[k][dest]+=cost;
while(tata[k]!=0)
{
int t=tata[k];
F[t][k]+=cost;
F[k][t]-=cost;
k=t;
}
}
}
}
}
void solve()
{
fluxMaxim();
ofstream fout("harta.out");
fout<<flux<<"\n";
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
if(i!=j && F[i][j+n]==1)
fout<<i<<" "<<j<<"\n";
}
fout.close();
}
int main()
{
citire();
solve();
return 0;
}