Pagini recente » Cod sursa (job #2355994) | Cod sursa (job #1177546) | Cod sursa (job #1567851) | Cod sursa (job #2894916) | Cod sursa (job #1166176)
#include<fstream>
#include<list>
#include<vector>
#include<bitset>
#include<cmath>
#include<algorithm>
#define DMAX 402
#define INF 0x3f3f3f3f
using namespace std;
ifstream fin ("adapost.in");
ofstream fout("adapost.out");
list<int> lista;
list<int>::iterator it;
vector< list<int> > l(DMAX,lista);
bitset<DMAX>viz;
struct coord{double x,y;}cs[DMAX],ca[DMAX];
int n,i,j,s,d;
int dad[DMAX];
int cap[DMAX][DMAX],flx[DMAX][DMAX],que[DMAX];
double cst[DMAX][DMAX],dst[DMAX],dmax,sumd,c;
double calc_dist(int i, int j)
{
double d;
d=sqrt((cs[i].x-ca[j].x)*(cs[i].x-ca[j].x)+(cs[i].y-ca[j].y)*(cs[i].y-ca[j].y));
return d;
}
int bf()
{
int ls=0,ld=0,x,y;
for(i=0;i<=d;++i)
{
dst[i]=INF;
dad[i]=0;
}
viz=0;
dst[s]=1;
viz[s]=0;
que[0]=s;
while(ls<=ld)
{
x=que[ls++];
viz[x]=0;
for(it=l[x].begin();it!=l[x].end();++it)
{
y=*it;
c=cst[x][y];
if(dst[y]-dst[x]-c>0.005 && cap[x][y]>flx[x][y])
{
dst[y]=dst[x]+c;
dad[y]=x;
if(!viz[y])
{
viz[y]=1;
que[++ld]=y;
}
}
}
}
if(dst[d]<INF)
{
int flow=INF;
for(i=d;i>0;i=dad[i])
flow=min(flow,cap[dad[i]][i]-flx[dad[i]][i]);
if(flow!=INF)
{
for(i=d;i>0;i=dad[i])
{
flx[dad[i]][i]+=flow;
flx[i][dad[i]]-=flow;
sumd+=flow*cst[dad[i]][i];
dmax=max(dmax,flow*cst[dad[i]][i]);
}
}
return 1;
}
return 0;
}
int main()
{
fin>>n;
for(i=1;i<=n;++i)
fin>>cs[i].x>>cs[i].y;
for(i=1;i<=n;++i)
fin>>ca[i].x>>ca[i].y;
s=0; d=n+n+1;
for(i=1;i<=n;++i)
{
l[s].push_back(i);
l[i].push_back(s);
cap[0][i]=1;
}
for(i=n+1;i<d;++i)
{
l[i].push_back(d);
l[d].push_back(i);
cap[i][d]=1;
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
{
l[i].push_back(j+n);
l[j+n].push_back(i);
cst[i][j+n]=calc_dist(i,j);
cst[j+n][i]=-cst[i][j+n];
cap[i][j+n]=1;
}
while(bf())
{
}
fout<<dmax<<" "<<sumd;
return 0;
}