Pagini recente » Cod sursa (job #1839153) | Cod sursa (job #2060092) | Cod sursa (job #459005) | Cod sursa (job #1683831) | Cod sursa (job #2960856)
#include <fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
bool exists[1005];
int pre[1005],C[1005][1005],flux[1005][1005],n;
vector <int> adj[1005];
queue <int> coada;
void bfs()
{
int nod,vecin,i;
for(i=0;i<=2*n+1;i++) {exists[i]=0; pre[i]=0;}
exists[0]=1;
pre[0]=-1;
coada.push(0);
while(!coada.empty())
{
nod=coada.front();
coada.pop();
for(i=0;i<adj[nod].size();i++)
{
vecin=adj[nod][i];
if (!exists[vecin] && C[nod][vecin]> flux[nod][vecin])
{
exists[vecin]=1;
pre[vecin]=nod;
coada.push(vecin);
}
}
}
}
int main()
{
int i,m,fluxtotal=0,mini,x,y,c,nod,urm,s,d;
cin>>n;
s=0;
d=2*n+1;
for(i=1;i<=n;i++)
{
cin>>x>>y;
C[s][i]=y;
C[n+i][d]=x;
adj[s].push_back(i);
adj[i].push_back(s);
adj[d].push_back(n+i);
adj[n+i].push_back(d);
for(int j=1;j<=n;j++)
if(i!=j){
C[i][n+j]=1;
adj[i].push_back(n+j);
adj[n+j].push_back(i);
}
}
while(true)
{
bfs();
if(exists[d]==0) break;
for(i=0;i<adj[d].size();i++)
if (exists[adj[d][i]] && C[adj[d][i]][d]>flux[adj[d][i]][d])
{
nod=adj[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=adj[d][i];
urm=d;
while(nod>=0)
{
flux[nod][urm]+=mini;
flux[urm][nod]-=mini;
urm=nod;
nod=pre[nod];
}
}
fluxtotal=fluxtotal+mini;
}
}
cout<<fluxtotal<<'\n';
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(flux[i][j]==1)
cout<<j-n<<" "<<i<<'\n';
return 0;
}