Pagini recente » Cod sursa (job #123031) | Cod sursa (job #1188931) | Cod sursa (job #1056550) | Cod sursa (job #372391) | Cod sursa (job #2960206)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
bool apare[1005];
int pre[1005],C[1005][1005],flux[1005][1005],n;
vector <int> G[1005];
queue <int> Q;
void bfs();
int main()
{
int i,m,fluxtotal=0,mini,x,y,c,nod,urm,s,d;
fin>>n;
s=0;
d=2*n+1;
for(i=1;i<=n;i++)
{
fin>>x>>y;
C[s][i]=y;
C[n+i][d]=x;
G[s].push_back(i);
G[i].push_back(s);
G[d].push_back(n+i);
G[n+i].push_back(d);
for(int j=1;j<=n;j++)
if(i!=j){
C[i][n+j]=1;
G[i].push_back(n+j);
G[n+j].push_back(i);
}
}
while(1)
{
bfs();
if(!apare[d]) break;
for(i=0;i<G[d].size();i++)
if (apare[G[d][i]] && C[G[d][i]][d]>flux[G[d][i]][d])
{
nod=G[d][i];
urm=d;
mini=C[nod][urm]-flux[nod][urm];
while(nod>=0)
{
mini=min(mini, C[nod][urm]-flux[nod][urm]);
urm=nod;
nod=pre[nod];
}
if(mini)
{
nod=G[d][i];
urm=d;
while(nod>=0)
{
flux[nod][urm]+=mini;
flux[urm][nod]-=mini;
urm=nod;
nod=pre[nod];
}
}
fluxtotal+=mini;
}
}
fout<<fluxtotal<<'\n';
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(flux[i][j]==1)
fout<<j-n<<" "<<i<<'\n';
return 0;
}
void bfs()
{
int nod,vecin,i;
for(i=0;i<=2*n+1;i++) {apare[i]=0; pre[i]=0;}
apare[0]=1;
pre[0]=-1;
Q.push(0);
while(!Q.empty())
{
nod=Q.front();
Q.pop();
for(i=0;i<G[nod].size();i++)
{
vecin=G[nod][i];
if (!apare[vecin] && C[nod][vecin]> flux[nod][vecin])
{
apare[vecin]=1;
pre[vecin]=nod;
Q.push(vecin);
}
}
}
}