Pagini recente » Cod sursa (job #533177) | Cod sursa (job #2373654) | Cod sursa (job #3228395) | Cod sursa (job #1722422) | Cod sursa (job #791608)
Cod sursa(job #791608)
#include <cstdio>
#include <vector>
using namespace std;
#define nmax 210
#define inf 1<<30
int c[nmax][nmax], f[nmax][nmax], u[nmax], t[nmax], q[nmax], fm, n, sol;
vector <int> g[nmax];
int min(int a, int b)
{
if (a>b) a=b;
return a;
}
int bf()
{
int i, y, j, h=1, x, nod;
for (i=0; i<=2*n+1; i++) u[i]=0;
q[1]=0;
u[0]=1;
for (y=1; y<=h; y++)
{
i=q[y];
for (j=0; j<g[i].size(); j++)
{
nod=g[i][j];
if (!u[nod])
if (c[i][nod]!=f[i][nod])
{
u[nod]=1;
q[++h]=nod;
t[nod]=i;
if (nod==2*n+1) return 1;
}
}
}
return 0;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&n);
int i, j, x, y, nod;
for (i=1; i<=n; i++)
{
scanf("%d %d",&x, &y);
g[0].push_back(i);
g[i].push_back(0);
g[n+i].push_back(2*n+1);
g[2*n+1].push_back(n+i);
c[0][i]=x;
c[n+i][2*n+1]=y;
for (j=1; j<=n; j++)
if (i!=j)
{
g[i].push_back(n+j);
g[n+j].push_back(i);
c[i][n+j]=1;
}
}
while (bf())
{
nod=2*n+1;
fm=inf;
while (nod)
{
fm=min(fm, c[t[nod]][nod]-f[t[nod]][nod]);
nod=t[nod];
}
nod=2*n+1;
while (nod)
{
f[t[nod]][nod]+=fm;
f[nod][t[nod]]-=fm;
nod=t[nod];
}
}
for (i=1; i<=n; i++)
for (j=0; j<g[i].size(); j++)
{
nod=g[i][j];
if (c[i][nod]==f[i][nod] && nod) sol++;
}
printf("%d\n",sol);
for (i=1; i<=n; i++)
for (j=0; j<g[i].size(); j++)
{
nod=g[i][j];
if (c[i][nod]==f[i][nod] && nod) printf("%d %d\n",i,nod-n);
}
}