Pagini recente » Cod sursa (job #963359) | Cod sursa (job #1206429) | Cod sursa (job #1292518) | Istoria paginii runda/mere/clasament | Cod sursa (job #1524765)
#include <fstream>
#include <string.h>
#include <limits.h>
#include <vector>
#define nMax 205
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int C[nMax][nMax], F[nMax][nMax], TT[nMax], q[nMax], nod, V, i, a, b, fmin, viz[nMax], S, D, Sum, n, j;
vector<int> G[nMax];
int BF()
{
memset(viz, 0, sizeof(viz));
q[0]=viz[S]=1;
q[1]=S;
for(int i=1;i<=q[0];i++)
{
nod=q[i];
if(nod==D)
continue;
for(int j=0;j<G[nod].size();j++)
{
V=G[nod][j];
if(viz[V] || C[nod][V]==F[nod][V])
continue;
q[++q[0]]=V;
viz[V]=1;
TT[V]=nod;
}
}
return viz[D];
}
void maxflow()
{
for(;BF();)
for(size_t i=0;i<G[D].size();i++)
{
nod=G[D][i];
if(!viz[nod] || C[nod][D]==F[nod][D])
continue;
TT[D]=nod;
fmin=INT_MAX;
for(nod=D;nod!=S;nod=TT[nod])
fmin=min(fmin, C[TT[nod]][nod]-F[TT[nod]][nod]);
if(fmin==0)
continue;
for(nod=D;nod!=S;nod=TT[nod])
{
F[TT[nod]][nod]+=fmin;
F[nod][TT[nod]]-=fmin;
}
}
}
int main()
{
fin>>n;
S=201, D=202;
for(i=1;i<=n;i++)
{
fin>>a>>b;
Sum+=a+b;
G[S].push_back(i);
G[i+100].push_back(S);
G[i+100].push_back(D);
G[D].push_back(i+100);
C[S][i]=a;
C[i+100][D]=b;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
C[i][j+100]=1;
G[i].push_back(j+100);
G[j+100].push_back(i);
}
maxflow();
fout<<Sum/2<<'\n';
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(F[i][j+100])
fout<<i<<" "<<j<<'\n';
return 0;
}