Pagini recente » Cod sursa (job #556799) | Cod sursa (job #38203) | Cod sursa (job #1140911) | Cod sursa (job #697806) | Cod sursa (job #830001)
Cod sursa(job #830001)
#include<fstream>
#include<string>
using namespace std;
int a[202][202],b[202][202],t[202],l[300];
int n,m,i,j,x,y;
ifstream f("harta.in");
ofstream g("harta.out");
inline int bf()
{
int st,dr;
st=0;
dr=0;
l[0]=0;
//memset(t,0,sizeof(t));
while(st<=dr)
{
x=l[st];
for(i=1;i<=2*n+1;i++)
if(a[x][i]-b[x][i]>0 && !t[i])
{
t[i]=x;
l[++dr]=i;
if(i==2*n+1)
return 1;
}
st++;
}
return 0;
}
inline void flux()
{
while(bf())
{
x=2*n+1;
while(x!=0)
{
b[t[x]][x]++;
b[x][t[x]]--;
x=t[x];
}
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
{if(i!=j-n && b[i][j]==1)
g<<i<<" "<<j-n<<"\n";}
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>x>>y;
a[0][i]=x;
a[n+i][2*n+1]=y;
m+=x;
}
g<<m<<"\n";
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(i!=j-n)
a[i][j]=1;
flux();
return 0;
}