Pagini recente » Cod sursa (job #2262231) | Cod sursa (job #2056631) | Cod sursa (job #1232369) | Cod sursa (job #458757) | Cod sursa (job #2617278)
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
const int lim=205;
vector<int> vec[lim];
int c[lim][lim];
int pred[lim];
queue<int> q;
int main()
{
int n,out,in,nr,m=0;
cin>>n;
nr=2*n+1;
for(int i=1;i<=n;++i)
{
cin>>out>>in;
vec[0].push_back(i); vec[i].push_back(0);
vec[i+n].push_back(nr); vec[nr].push_back(i+n);
c[0][i]=in;
c[i+n][nr]=out;
m+=out;
}
for(int i=1;i<=n;++i)
for(int j=n+1;j<nr;++j)
if(i+n!=j)
{
vec[i].push_back(j); vec[j].push_back(i);
c[i][j]=1;
}
cout<<m<<'\n';
int flow=0,ads;
do
{
for(int i=1;i<=nr;++i)
pred[i]=0;
pred[0]=-1;
q.push(0);
while(!q.empty())
{
int x=q.front();
q.pop();
for(auto y:vec[x])
if(c[x][y]>0 and pred[y]==0)
{
pred[y]=x;
q.push(y);
}
}
if(pred[nr]>0)
for(auto t:vec[nr])
if(pred[t]>0 and c[t][nr]>0)
{
ads=c[t][nr];
for(int k=t;pred[k]>0;k=pred[k])
ads=min(ads,c[pred[k]][k]);
c[t][nr]-=ads;
c[nr][t]+=ads;
for(int k=t;pred[k]>0;k=pred[k])
{
c[pred[k]][k]-=ads;
c[k][pred[k]]+=ads;
}
flow+=ads;
}
}while(pred[nr]>0);
for(int i=1;i<=n;++i)
for(int j=n+1;j<nr;++j)
if(i+n!=j and c[i][j]==0)
cout<<i<<' '<<j-n<<'\n';
return 0;
}