Pagini recente » Cod sursa (job #497004) | Cod sursa (job #1095542) | Cod sursa (job #878609) | Cod sursa (job #626379) | Cod sursa (job #641082)
Cod sursa(job #641082)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
int i,j,n,m,c[205][205],flux[205][205],x,y,tata[205],minim,flux_maxim,sink;
vector<int> lista[205];
queue<int> coada;
int viz[205];
ifstream f("harta.in");
ofstream g("harta.out");
int bf()
{
memset(viz,0,sizeof(viz));
memset(tata,0,sizeof(tata));
int x,i,nr_vecini,vecin;
coada.push(0);
while(!coada.empty())
{
x=coada.front(); coada.pop();
nr_vecini=lista[x].size();
for(i=0;i<nr_vecini;i++)
{
vecin=lista[x][i];
if(!viz[vecin]&&flux[x][vecin]<c[x][vecin])
{
viz[vecin]=1;
tata[vecin]=x;
coada.push(vecin);
}
}
}
return viz[n];
}
int main()
{
f>>n;
sink=2*n+1;
for(i=1;i<=n;i++)
{
f>>x>>y;
lista[0].push_back(i);
lista[i].push_back(0);
lista[i+n].push_back(sink);
lista[sink].push_back(i+n);
c[0][i]=x;
c[i+n][sink]=y;
}
for(i=1;i<=n;++i)
for(j=n+1;j<sink;++j)
if(j-i!=n)
{
lista[i].push_back(j);
c[i][j]=1;
lista[j].push_back(i);
c[j][i]=0;
}
while(bf())
{
for(i=0;i<sink;i++)
if(tata[i] && flux[i][sink]<c[i][sink])
{
minim=c[i][sink]-flux[i][sink];
for(j=i;j!=0;j=tata[j])
if(c[tata[j]][j]-flux[tata[j]][j]<minim)
minim=c[tata[j]][j]-flux[tata[j]][j];
if(minim)
{
flux[i][sink]=flux[i][sink]+ minim;
flux[sink][i]=flux[sink][i]- minim;
for(j=i;j!=0;j=tata[j])
{
flux[tata[j]][j]=flux[tata[j]][j]+ minim;
flux[j][tata[j]]=flux[j][tata[j]]-minim;
}
flux_maxim=flux_maxim+minim;
}
}
}
g<<flux_maxim<<'\n';
for(i=1;i<=n;++i)
for(j=n+1;j<sink;++j)
if(flux[i][j]) g<<i<<' '<<j-n<<'\n';
f.close();g.close();
return 0;
}