Pagini recente » Cod sursa (job #2985886) | Cod sursa (job #3032262) | Cod sursa (job #508565) | Cod sursa (job #1425579) | Cod sursa (job #708817)
Cod sursa(job #708817)
#include<stdio.h>
#include<vector>
using namespace std;
FILE*f=fopen("harta.in","r");
FILE*g=fopen("harta.out","w");
int n,nn,sol,p,u,minn,nod,c[204][204],L[204][204],viz[204],d[204],t[204];
struct nod
{
int in,out;
}w[101];
vector <int> v[204];
int df()
{
int ok=0;
for(int i=0;i<=nn;++i)
viz[i]=0;
p=u=1;
d[1]=0;
viz[0]=1;
while(p<=u)
{
for(int i=0;i<v[d[p]].size();++i)
if(!viz[v[d[p]][i]]&&c[d[p]][v[d[p]][i]]-L[d[p]][v[d[p]][i]]>0)
{
if(v[d[p]][i]==nn)
ok=1;
else
{
t[v[d[p]][i]]=d[p];
d[++u]=v[d[p]][i];
viz[v[d[p]][i]]=1;
}
}
++p;
}
return ok;
}
void dfs()
{
for(int i=1;i<=n;++i)
for(int j=n+1;j<nn;++j)
if(L[i][j])
fprintf(g,"%d %d\n",i,j-n);
}
int main()
{
fscanf(f,"%d",&n);
for(int i=1;i<=n;++i)
fscanf(f,"%d%d",&w[i].out,&w[i].in);
for(int i=1;i<=n;++i)
for(int 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;
}
for(int i=1;i<=n;++i)
{
v[0].push_back (i);
v[i].push_back (0);
v[i+n].push_back (2*n+1);
v[2*n+1].push_back (i+n);
c[0][i]=w[i].out;
c[i+n][2*n+1]=w[i].in;
}
nn=2*n+1;
while(df())
{
for(int ii=0;ii<n;++ii)
{
minn=c[v[nn][ii]][nn]-L[v[nn][ii]][nn];
for(int nod=v[nn][ii];nod;nod=t[nod])
if(c[t[nod]][nod]-L[t[nod]][nod]<minn)
minn=c[t[nod]][nod]-L[t[nod]][nod];
L[v[nn][ii]][nn]+=minn;
L[nn][v[nn][ii]]-=minn;
for(int nod=v[nn][ii];nod;nod=t[nod])
{
L[t[nod]][nod]+=minn;
L[nod][t[nod]]-=minn;
}
sol+=minn;
}
}
fprintf(g,"%d\n",sol);
dfs();
fclose(g);
fclose(f);
return 0;
}