Pagini recente » Cod sursa (job #290501) | Cod sursa (job #2506354) | Cod sursa (job #803678) | Cod sursa (job #2506349) | Cod sursa (job #2666877)
#include <bits/stdc++.h>
using namespace std;
ifstream in("harta.in");
ofstream out("harta.out");
vector<int> vec[205];
int c[205][205];
int last[205];
queue<int> q;
int main()
{
int n,x,y,s=0;
in>>n;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j) if(i!=j)
{
c[i][j+n]=1;
vec[i].push_back(j+n);
vec[j+n].push_back(i);
}
for(int i=1;i<=n;++i)
{
c[i+n][i]=n;
vec[i].push_back(i+n);
vec[i+n].push_back(i);
in>>x>>y;
s+=x;
c[0][i]=x;
vec[0].push_back(i);
vec[i].push_back(0);
c[i+n][2*n+1]=y;
vec[i+n].push_back(2*n+1);
vec[2*n+1].push_back(i+n);
}
do
{
last[0]=-2;
for(int i=1;i<=2*n+1;++i)
last[i]=-1;
q.push(0);
while(!q.empty())
{
int x=q.front(); q.pop();
for(int y:vec[x])
if(last[y]==-1 and c[x][y]>0)
{
last[y]=x;
q.push(y);
}
}
if(last[2*n+1]>=0)
for(int x:vec[2*n+1])
if(c[x][2*n+1]>0 and last[x]>=0)
{
int minim=c[x][2*n+1];
for(int u=x;last[u]>=0;u=last[u])
minim=min(minim,c[last[u]][u]);
if(minim==0) continue;
c[x][2*n+1]-=minim;
c[2*n+1][x]+=minim;
for(int u=x;last[u]>=0;u=last[u])
{
c[last[u]][u]-=minim;
c[u][last[u]]+=minim;
}
}
}while(last[2*n+1]>=0);
out<<s<<'\n';
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j and c[i][j+n]==0)
out<<i<<' '<<j<<'\n';
return 0;
}