Pagini recente » Cod sursa (job #2146270) | Cod sursa (job #967367) | Monitorul de evaluare | Cod sursa (job #995438) | Cod sursa (job #581686)
Cod sursa(job #581686)
#include <fstream>
using namespace std;
const int N=205;
int cap[N][N],flux[N][N],T[N],v[N],n;
bool use[N];
ifstream in("harta.in");
ofstream out("harta.out");
bool bfs(int X,int Y)
{
int i,x,st=0,dr=0;
for (i=1;i<=n;i++)
{
use[i]=false;
T[i]=0;
}
v[++dr]=X;
use[X]=true;
while (st<dr)
{
x=v[++st];
for (i=1;i<=n;i++)
if (!use[i] && cap[x][i]>flux[x][i])
{
v[++dr]=i;
T[i]=x;
use[i]=true;
}
}
return use[Y];
}
void max_flow(int X,int Y)
{
int M,i,j;
while (bfs(X,Y))
for (i=0;i<=n;i++)
if (cap[i][Y]>flux[i][Y])
{
M=cap[i][Y]-flux[i][Y];
if (!M)
continue;
for (j=i;j!=X;j=T[j])
M=min(M,cap[T[j]][j]-flux[T[j]][j]);
if (!M)
continue;
T[Y]=i;
for (j=Y;j!=X;j=T[j])
{
flux[T[j]][j]+=M;
flux[j][T[j]]-=M;
}
}
}
int main()
{
int m,i,j,nr=0;
in>>m;n=2*m+1;
for (i=1;i<=m;i++)
{
in>>cap[0][i]>>cap[i+m][n];
for (j=m+1;j<n;j++)
cap[i][j]=1;
cap[i][i+m]=0;
}
max_flow(0,n);
for (i=1;i<=m;i++)
for (j=m+1;j<n;j++)
if (flux[i][j]>0)
nr++;
out<<nr<<"\n";
for (i=1;i<=m;i++)
for (j=m+1;j<n;j++)
if (flux[i][j]>0)
out<<i<<" "<<j-m<<"\n";
return 0;
}