Pagini recente » Istoria paginii utilizator/voiky | Istoria paginii utilizator/xeodor | Cod sursa (job #1210725) | Profil roxana.tololoi | Cod sursa (job #1790149)
#include <iostream>
#include<fstream>
#include<queue>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
const int nmax=805;
int fl[nmax][nmax],c[nmax][nmax],v[nmax][nmax];
int G[nmax],q[nmax],prec[nmax],l[nmax],r[nmax];
double d[nmax][nmax],cost[nmax],dist[nmax*nmax],x1[nmax],y11[nmax],x2[nmax],y2[nmax],costul;
const double eps=0.0000001;
int i,n,m,j,sink,source,node,start,u,p,flow,k,cuplaj;
bool inq[nmax],viz[nmax];
bool ok,change;
bool pairup(int xx)
{
if(viz[xx]) return 0;
viz[xx]=1;
for(int j=1;j<=G[xx];j++)
{
int node=v[xx][j];
if(node!=source&&r[node]==0||pairup(r[node]))
{
l[xx]=node;
r[node]=xx;
return 1;
}
}
return 0;
}
bool bf()
{
for(i=1;i<=sink;i++)
prec[i]=0,cost[i]=(1<<30),inq[i]=0;
queue<int> qbf;
qbf.push(source);
prec[source]=-1;cost[source]=0;
while(!qbf.empty())
{
start=qbf.front();qbf.pop();
inq[start]=0;
for(i=1;i<=G[start];i++)
{
node=v[start][i];
if(cost[node]-(cost[start]+d[start][node])>eps&&fl[start][node]<c[start][node])
{
if(!inq[node]) {qbf.push(node);inq[node]=1;}
cost[node]=cost[start]+d[start][node];
prec[node]=start;
}
}
}
return (cost[sink]!=(1<<30));
}
bool check(int x)
{
for(i=1;i<=n;i++)
{
G[i]=1;G[n+i]=1;
l[i]=0;r[n+i]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(d[i][n+j]<=dist[x])
{
G[i]++;G[n+j]++;
v[i][G[i]]=n+j;
v[n+j][G[n+j]]=i;
}
}
change=1;cuplaj=0;
while(change)
{
change=0;
for(i=1;i<=n;i++)
viz[i]=0;
for(i=1;i<=n;i++)
{
if(l[i]==0&&pairup(i))
change=1;
}
}
for(i=1;i<=n;i++)
{
if(l[i]!=0) cuplaj++;
}
return (cuplaj==n);
}
int main()
{
ifstream f("adapost.in");
ofstream g("adapost.out");
f>>n;source=2*n+1;sink=2*n+2;
for(i=1;i<=n;i++)
{
f>>x1[i]>>y11[i];
}
for(i=1;i<=n;i++)
{
f>>x2[i]>>y2[i];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
d[i][n+j]=sqrt((x1[i]-x2[j])*(x1[i]-x2[j])+(y11[i]-y2[j])*(y11[i]-y2[j]));
d[n+j][i]=d[i][n+j]*(-1);
c[i][n+j]=1;
k++;
dist[k]=d[i][n+j];
}
for(i=1;i<=n;i++)
{
G[source]++;
v[source][G[source]]=i;
c[source][i]=1;
G[i]++;
v[i][G[i]]=source;
G[n+i]++;
v[n+i][G[n+i]]=sink;
c[n+i][sink]=1;
}
sort(dist+1,dist+k+1);
int pr=1,ul=k;
while(ul-pr>1)
{
m=(pr+ul)/2;
if(check(m)) ul=m;
else pr=m;
}
ok=check(ul);
while(bf())
{
node=sink;
while(node!=source)
{
fl[prec[node]][node]++;
fl[node][prec[node]]--;
node=prec[node];
}
costul+=cost[sink];
}
g<<fixed<<setprecision(6)<<dist[ul]<<' '<<costul;
return 0;
}