Pagini recente » Cod sursa (job #1508356) | Cod sursa (job #1136754) | Cod sursa (job #2710590) | Cod sursa (job #2660654) | Cod sursa (job #2605277)
#include <fstream>
#include <queue>
#include <vector>
#define inf 2000000000
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<int> g[205];
queue<int> q;
int tata[205];
int f[205][205],c[205][205],cost[205][205];
struct grad
{
int in, out;
}v[101];
bool viz[205];
int n,m,x,y;
long long sol;
bool bfs(int st, int dst)
{
q.empty();
q.push(st);
for(int i=1;i<=2*n+1;i++)
viz[i]=tata[i]=0;
viz[st]=1;
while(!q.empty())
{
int nod=q.front();
q.pop();
for(int i=0;i<g[nod].size();i++)
{
int nou=g[nod][i];
if(viz[nou]==0&&c[nod][nou]-f[nod][nou]>0)
{
viz[nou]=1;
tata[nou]=nod;
q.push(nou);
}
}
}
return viz[dst];
}
int minim(int nod)
{
int Min=c[nod][2*n+1]-f[nod][2*n-1];
while(nod!=0)
{
int nou=tata[nod];
Min=min(Min,c[nou][nod]-f[nou][nod]);
nod=nou;
}
return Min;
}
void add(int val,int nod)
{
f[nod][2*n+1]+=val;
f[2*n+1][nod]-=val;
while(nod!=0)
{
int nou=tata[nod];
f[nou][nod]+=val;
f[nod][nou]-=val;
nod=nou;
}
}
int main()
{
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>v[i].in>>v[i].out;
m+=v[i].in;
}
fout<<m<<'\n';
for(int i=1;i<=n;i++)
{
g[0].push_back(i);
g[i].push_back(0);
g[n+i].push_back(2*n+1);
g[2*n+1].push_back(n+i);
c[0][i]=v[i].in;
c[i+n][2*n+1]=v[i].out;
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(i!=j-n)
{
g[i].push_back(j);
g[j].push_back(i);
c[i][j]=1;
}
while(bfs(0,2*n+1))
for(int i=0;i<g[2*n+1].size();i++)
{
int nod=g[2*n+1][i];
if (f[nod][2*n+1]==c[nod][2*n+1]||viz[nod]==0)
continue;
int qmin=minim(nod);
add(qmin,nod);
}
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n;j++)
if(f[i][j]>0)
fout<<i<<' '<<j-n<<'\n';
return 0;
}