Pagini recente » Cod sursa (job #1069163) | Cod sursa (job #1223483) | Cod sursa (job #100100) | Cod sursa (job #656829) | Cod sursa (job #1069696)
#include <algorithm>
#include <fstream>
#include <bitset>
#include <vector>
#include <queue>
#define INF 0x3f3f3f3f
#define PII pair<int, int>
#define x first
#define y second
using namespace std;
const int N=300;
ifstream fin("harta.in");
ofstream fout("harta.out");
int C[N][N], F[N][N], degin[N], degout[N], Tr[N];
vector <int> g[N];
vector <PII> sol;
bitset <N> v;
int n;
int bfs()
{
int x;
queue <int> Q;
v.reset();
v[0]=1;
for(Q.push(0);!Q.empty();Q.pop())
{
x=Q.front();
if(x==2*n+1) continue;
for(auto p: g[x])
{
if(C[x][p]==F[x][p]||v[p]) continue;
v[p]=1;
Q.push(p);
Tr[p]=x;
}
}
return v[2*n+1];
}
void get_flow()
{
int i, fmin;
while(bfs())
{
for(auto p: g[2*n+1])
{
if(F[p][2*n+1]==C[p][2*n+1]||!v[p]) continue;
Tr[2*n+1]=p;
fmin=INF;
for(i=2*n+1;i;i=Tr[i])
{
fmin=min(fmin, C[Tr[i]][i]-F[Tr[i]][i]);
}
if(!fmin) continue;
for(i=2*n+1;i;i=Tr[i])
{
F[Tr[i]][i]+=fmin;
F[i][Tr[i]]-=fmin;
}
}
}
}
int main()
{
int i, j;
fin>>n;
for(i=1;i<=n;i++) fin>>degin[i]>>degout[i];
for(i=1;i<=n;i++)
{
C[0][i]=degin[i];
g[0].push_back(i);
g[i].push_back(0);
C[i+n][2*n+1]=degout[i];
g[i+n].push_back(2*n+1);
g[2*n+1].push_back(i+n);
for(j=n+1;j<2*n+1;j++)
{
if(i!=j-n)
{
C[i][j]=1;
g[i].push_back(j);
g[j].push_back(i);
}
}
}
get_flow();
for(i=1;i<=n;i++)
{
for(j=n+1;j<2*n+1;j++)
{
if(F[i][j]==1) sol.push_back(make_pair(i, j-n));
}
}
fout<<sol.size()<<"\n";
for(auto it: sol) fout<<it.x<<" "<<it.y<<"\n";
fin.close();
fout.close();
}