Pagini recente » Cod sursa (job #3168294) | Cod sursa (job #616961) | Cod sursa (job #1469073) | Cod sursa (job #3190938) | Cod sursa (job #1240965)
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
vector<int> v[210];
queue<int> q;
char vaz[210];
int c[210][210],flow[210][210],tata[210],n,m;
int bfs()
{
memset(vaz,0,sizeof(vaz));
q.push(0);
while(!q.empty())
{
int nod=q.front();q.pop();
for(vector<int>::iterator it=v[nod].begin();it!=v[nod].end();it++)
if(!vaz[*it] && c[nod][*it]>flow[nod][*it])
{
vaz[*it]=1;
q.push(*it);
tata[*it]=nod;
}
}
return vaz[m];
}
int main()
{
freopen("harta.in", "r", stdin);
freopen("harta.out", "w", stdout);
scanf("%d",&n);
int sol=0,x,y;
m=2*n+1;
for(int i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
v[0].push_back(i);v[i].push_back(0);
v[i+n].push_back(m);v[m].push_back(i+n);
c[0][i]=x;
c[i+n][m]=y;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j)
{
v[i].push_back(j+n);v[j+n].push_back(i);
c[i][j+n]=1;
}
while(bfs())
{
for(vector<int>::iterator it=v[m].begin();it!=v[m].end();it++)
if(vaz[*it] && c[*it][m]>flow[*it][m])
{
tata[m]=*it;
int s=10000;
for(int i=m;i;i=tata[i]) s=min(s,c[tata[i]][i]-flow[tata[i]][i]);
for(int i=m;i;i=tata[i])
{
flow[tata[i]][i]+=s;
flow[i][tata[i]]-=s;
}
sol+=s;
}
}
printf("%d\n",sol);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && flow[i][j+n]>0) printf("%d %d\n",i,j);
return 0;
}