Pagini recente » Cod sursa (job #789272) | Cod sursa (job #562520) | Cod sursa (job #562524)
Cod sursa(job #562524)
#include <fstream>
#include <list>
#include <queue>
#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 S,D,N,C[MaxN][MaxN],F[MaxN][MaxN],T[MaxN];
int x,y;
list<int> A[MaxN];
inline bool BFS()
{
bool ok=false;
int V[MaxN];
memset(V,0,sizeof(V));
V[S]=1;
queue<int> q;
q.push(S);
while(!q.empty())
{
int nod=q.front();
q.pop();
V[nod]=1;
for(list<int>::iterator it=A[nod].begin();it!=A[nod].end();++it)
{
if(!V[*it] && C[nod][*it]>F[nod][*it])
{
if(*it==D)
{
ok=true;
continue;
}
else
{
T[*it]=nod;
q.push(*it);
}
}
}
}
return ok;
}
inline int flux()
{
int maxflow=0;
while(BFS())
{
for(list<int>::iterator it=A[D].begin();it!=A[D].end();++it)
{
int nod=*it;
int minim=C[nod][D]-F[nod][D];
while(nod!=9 && nod!=0)
{
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(nod!=9 && nod!=0)
{
F[T[nod]][nod]+=minim;
F[nod][T[nod]]-=minim;
nod=T[nod];
}
maxflow+=minim;
}
}
return maxflow;
}
int main()
{
fin>>N;
S=(N<<1)+1;
D=S+1;
for(register int i=1;i<=N;++i)
{
for(register int j=1;j<=N;++j)
{
if(i!=j)
{
A[i].push_back(j+N);
A[j+N].push_back(i);
C[i][j+N]=1;
}
}
}
for(register int i=1;i<=N;++i)
{
fin>>x>>y;
int nod2=i+N;
A[S].push_back(i);
A[i].push_back(S);
A[nod2].push_back(D);
A[D].push_back(nod2);
C[S][i]=x;
C[nod2][D]=y;
}
fin.close();
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;
}