Pagini recente » Cod sursa (job #1692479) | Cod sursa (job #1189919) | Cod sursa (job #284099) | Cod sursa (job #2143444) | Cod sursa (job #1444334)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
const char InFile[]="harta.in";
const char OutFile[]="harta.out";
const int MaxN=256;
ifstream fin(InFile);
ofstream fout(OutFile);
int N,x,y,S,D,T[MaxN],F[MaxN][MaxN],C[MaxN][MaxN],Q[MaxN];
vector<int> A[MaxN];
inline void connect(const int &nod1, const int &nod2, const int &c)
{
A[nod1].push_back(nod2);
A[nod2].push_back(nod1);
C[nod1][nod2]=c;
}
inline int BFS()
{
int V[MaxN];
memset(V,0,sizeof(V));
memset(T,0,sizeof(T));
Q[0]=0;
Q[++Q[0]]=S;
V[S]=1;
while(Q[0])
{
int nod=Q[Q[0]];
--Q[0];
for(vector<int>::iterator it=A[nod].begin();it!=A[nod].end();++it)
{
if(!V[*it] && C[nod][*it]>F[nod][*it])
{
T[*it]=nod;
V[*it]=1;
Q[++Q[0]]=*it;
}
}
}
return T[D];
}
inline int flux()
{
int flux_maxim=0;
while(BFS())
{
for(vector<int>::iterator it=A[D].begin();it!=A[D].end();++it)
{
int nod=*it;
int minim=C[nod][D]-F[nod][D];
while(T[nod])
{
minim=min(minim,C[T[nod]][nod]-F[T[nod]][nod]);
nod=T[nod];
}
nod=*it;
F[nod][D]+=minim;
F[D][nod]-=minim;
while(T[nod])
{
F[T[nod]][nod]+=minim;
F[nod][T[nod]]-=minim;
nod=T[nod];
}
flux_maxim+=minim;
}
}
return flux_maxim;
}
int main()
{
fin>>N;
S=(N<<1)+1;
D=S+1;
for(register int i=1;i<=N;++i)
{
fin>>x>>y;
connect(S,i,x);
connect(i+N,D,y);
}
fin.close();
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=N;++j)
{
if(i!=j)
{
connect(i,j+N,1);
}
}
}
fout<<flux()<<"\n";
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=N;++j)
{
if(i!=j)
{
if(C[i][j+N]==F[i][j+N])
{
fout<<i<<" "<<j<<"\n";
}
}
}
}
fout.close();
return 0;
}