Pagini recente » Rating Nervous (nervous) | Cod sursa (job #1083994) | Cod sursa (job #2899963) | Cod sursa (job #1233666) | Cod sursa (job #2402264)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("harta.in");
ofstream g ("harta.out");
const int nmax=3e2+3;
int n,m,act,ant[nmax],usu[nmax][nmax],p[nmax][nmax],sol,x,y,c;
bool viz[nmax];
vector <int> v[nmax];
vector < pair <int,int> > pwp;
queue <int> q;
bool solve()
{
memset(viz,0,sizeof(viz));
q.push(2*n+2);
viz[2*n+2]=1;
while(!q.empty())
{
int nod=q.front();
q.pop();
if(nod==2*n+1) continue;
for(int i=0;i<v[nod].size();++i)
{
int urm=v[nod][i];
if(usu[nod][urm]==p[nod][urm]||viz[urm]) continue;
q.push(urm);
viz[urm]=1;
ant[urm]=nod;
}
}
return viz[2*n+1];
}
int main()
{
ios::sync_with_stdio(false);
f>>n;
for(int i=1;i<=n;++i)
{
f>>x>>y;
usu[2*n+2][i]+=x;
v[2*n+2].push_back(i);
v[i].push_back(2*n+2);
usu[i+n][2*n+1]+=y;
v[i+n].push_back(2*n+1);
v[2*n+1].push_back(i+n);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i==j) continue;
usu[i][j+n]+=1;
v[i].push_back(j+n);
v[j+n].push_back(i);
}
}
while(true)
{
int ok=solve();
for(int i=0;i<v[2*n+1].size();++i)
{
int nod=v[2*n+1][i];
if(p[nod][2*n+1]==usu[nod][2*n+1]||!viz[nod]) continue;
ant[2*n+1]=nod;
act=2e9;
for(nod=2*n+1;nod!=2*n+2;nod=ant[nod]) act=min(act,usu[ant[nod]][nod]-p[ant[nod]][nod]);
if(!act) continue;
for(nod=2*n+1;nod!=2*n+2;nod=ant[nod])
{
p[ant[nod]][nod]+=act;
p[nod][ant[nod]]-=act;
}
sol+=act;
}
if(!ok) break;
}
g<<sol<<'\n';
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
{
if(i==j) continue;
if(p[i][j+n]) g<<i<<' '<<j<<'\n';
}
}
return 0;
}