Pagini recente » Istoria paginii utilizator/flavias | Istoria paginii utilizator/serbanmihnea | Profil M@2Te4i | Istoria paginii utilizator/nastase.roxana | Cod sursa (job #1172040)
#include<fstream>
#define pb push_back
#include<iomanip>
#include<cmath>
#include<queue>
#include<cstring>
#define N 220
#define FOR(a,b,c) for(int a=b;a<=c;++a)
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
vector<int> v[N];
queue<int> q;
int viz[N],n,m,F[N][N],C[N][N],T[N],a,x,y,des,nod,mi,t,st[N*N*N],dr[N*N*N];
int bfs(int x)
{
memset(viz,0,sizeof(viz));
q.push(0);
while(!q.empty())
{
nod=q.front();
q.pop();
if(nod==m)
continue;
FOR(i,0,v[nod].size()-1)
{
des=v[nod][i];
if(C[nod][des]==F[nod][des]||viz[des])
continue;
T[des]=nod;
viz[des]=1;
q.push(des);
}
}
return viz[m];
}
int main ()
{
f>>n;
m=2*n+1;
FOR(i,1,n)
{
f>>x>>y;
C[0][i]=x;
C[i+n][m]=y;
v[0].pb(i);
v[i].pb(0);
v[i+n].pb(m);
v[m].pb(i+n);
FOR(j,1,n)
{
if(i==j)
continue;
v[i].pb(j+n);
v[j+n].pb(i);
C[i][j+n]=1;
}
}
while(bfs(0))
{
FOR(i,0,v[m].size()-1)
{
if(!viz[v[m][i]]||C[v[m][i]][m]==F[v[m][i]][m])
continue;
T[m]=v[m][i];
a=m;
mi=(1<<30);
for(;a;a=T[a])
mi=min(mi,C[T[a]][a]-F[T[a]][a]);
a=m;
if(mi)
for(;a;a=T[a])
{
F[T[a]][a]+=mi;
F[a][T[a]]-=mi;
}
}
}
FOR(i,1,n)
FOR(j,1,n)
{
if(i==j)
continue;
if(F[i][j+n]==1)
{
st[++t]=i;
dr[t]=j;
}
}
g<<t<<"\n";
FOR(i,1,t)
g<<st[i]<<" "<<dr[i]<<"\n";
return 0;
}