Pagini recente » Cod sursa (job #1861203) | Cod sursa (job #2255350) | Cod sursa (job #3155081) | Cod sursa (job #3239954) | Cod sursa (job #3038496)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
///#include <tryhardmode>
///#include <GODMODE::ON>
using namespace std;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
const int INF=2e9;
const int NMAX=4e2+5;
vector<int>v[2*NMAX];
bool viz[2*NMAX];
int t[NMAX];
int flux[NMAX][NMAX];
int n,s,d;
bool bfs(int p)
{
int i;
for(i=0;i<=2*n+2;i++)
viz[i]=false;
queue<int>q;
q.push(p);
viz[p]=true;
while(!q.empty())
{
int p=q.front();
q.pop();
if(p==d)
return true;
for(auto i:v[p])
{
if(!viz[i] && flux[p][i]>0)
{
q.push(i);
t[i]=p;
viz[i]=true;
}
}
}
return false;
}
int main()
{
int m,i,j,mini=INF,x,y;
long long maxi=0;
fin>>n;
s=0;
d=2*n+1;
for(i=1;i<=n;i++)
{
fin>>x>>y;
v[s].push_back(i);
v[i].push_back(s);
v[i+n].push_back(d);
v[d].push_back(i+n);
flux[s][i]=x;
flux[i+n][d]=y;
for(j=1;j<=n;j++)
if(i==j)
continue;
else
{
flux[i][j+n]=1;
v[i].push_back(j+n);
v[j+n].push_back(i);
}
}
while(bfs(s))
{
for(auto i:v[d])
{
if(!viz[i] || flux[i][d]<=0)
continue;
mini=INF;
t[d]=i;
x=d;
while(x!=s)
{
mini=min(mini,flux[t[x]][x]);
x=t[x];
}
if(mini==0)
continue;
maxi+=mini;
x=d;
while(x!=s)
{
flux[x][t[x]]+=mini;
flux[t[x]][x]-=mini;
x=t[x];
}
}
}
fout<<maxi<<"\n";
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
if(flux[j+n][i]==1)
fout<<i<<" "<<j<<"\n";
}
return 0;
}