Pagini recente » Cod sursa (job #1663289) | Cod sursa (job #1935731) | Cod sursa (job #256524) | Cod sursa (job #1373938) | Cod sursa (job #2130252)
#include <fstream>
#include <vector>
#define DIM 203
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,m,i,mini,ve,a,b,cap,j;
vector< pair<int, int> > sol;
int c[DIM][DIM], f[DIM][DIM];
int d[DIM], z[DIM], t[DIM];
vector<int> v[DIM];
int bfs()
{
int p=1, u=1, i, nod,vecin;
for(i=0;i<=m;i++)
d[i]=0;
z[1]=0;
d[0]=1;
while(p<=u)
{
nod=z[p];
for(i=0;i<v[nod].size();i++)
{
vecin=v[nod][i];
if(c[nod][vecin]>f[nod][vecin]&&d[vecin]==0)
{
u++;
z[u]=vecin;
d[vecin]=1;
t[vecin]=nod;
}
}
p++;
}
return d[m];
}
int main()
{
fin>>n;
m=2*n+1;
for(i=1;i<=n;i++)
{
fin>>a>>b;
v[0].push_back(i);
c[0][i]=a;
v[i+n].push_back(m);
v[m].push_back(i+n);
c[i+n][m]=b;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
{
v[i].push_back(j+n);
v[j+n].push_back(i);
c[i][j+n]=1;
}
while(bfs()==1)
{
for(i=0;i<v[m].size();i++)
{
ve=v[m][i];
if(d[ve]==1&&c[ve][m]>f[ve][m])
{
a=ve;b=m;
mini=c[ve][m]-f[ve][m];
while(a!=0)
{
mini=min(mini, c[a][b]-f[a][b]);
b=a;a=t[a];
}
mini=min(mini, c[a][b]-f[a][b]);
a=ve;b=m;
while(a!=0)
{
f[a][b]+=mini;
f[b][a]-=mini;
b=a;a=t[a];
}
f[a][b]+=mini;
f[b][a]-=mini;
f[m][ve]+=mini;
}
}
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(f[i][j]==1)
sol.push_back(make_pair(i, j-n));
fout<<sol.size()<<"\n";
for(i=0;i<sol.size();i++)
fout<<sol[i].first<<" "<<sol[i].second<<"\n";
return 0;
}