Pagini recente » Cod sursa (job #493305) | pre_oni_gim2015 | Cod sursa (job #2892993) | Cod sursa (job #2650223) | Cod sursa (job #1789060)
#include <iostream>
#include<fstream>
#include<queue>
#include<algorithm>
#include<cmath>
using namespace std;
const int nmax=805;
int fl[nmax][nmax],c[nmax][nmax],v[nmax][nmax];
int G[nmax],q[nmax],prec[nmax];
double d[nmax][nmax],cost[nmax],dist[nmax*nmax],x1[nmax],y11[nmax],x2[nmax],y2[nmax],costul;
int i,n,m,j,sink,source,node,start,u,p,flow,k;
bool inq[nmax];
bool ok;
bool bfs()
{
for(i=1;i<=sink;i++)
prec[i]=0;
u=1;q[u]=source;
prec[source]=-1;p=1;
while(p<=u)
{
start=q[p];p++;
for(i=1;i<=G[start];i++)
{
node=v[start][i];
if(prec[node]==0&&fl[start][node]<c[start][node])
{
u++;
prec[node]=start;
q[u]=node;
if(node==sink) return 1;
}
}
}
return 0;
}
bool check(int x)
{
for(i=1;i<=n;i++)
{
G[i]=1;G[n+i]=1;
fl[source][i]=0;fl[i][source]=0;
fl[n+i][sink]=0;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
fl[i][n+j]=0;fl[n+j][i]=0;
if(d[i][n+j]<=dist[x]+0.0000001)
{
G[i]++;G[n+j]++;
v[i][G[i]]=n+j;
v[n+j][G[n+j]]=i;
}
}
flow=0;
while(bfs())
{
node=sink;
while(node!=source)
{
fl[prec[node]][node]++;
fl[node][prec[node]]--;
node=prec[node];
}
flow++;
}
return (flow==n);
}
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[start]+d[start][node]<cost[node]&&fl[start][node]<c[start][node])
{
if(!inq[i]) {qbf.push(node);inq[node]=1;}
cost[node]=cost[start]+d[start][node];
prec[node]=start;
}
}
}
return (cost[sink]!=(1<<30));
}
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];
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);
for(i=1;i<=sink;i++)
for(j=1;j<=sink;j++)
fl[i][j]=0;
while(bf())
{
node=sink;
while(node!=source)
{
fl[prec[node]][node]++;
fl[node][prec[node]]--;
node=prec[node];
}
costul+=cost[sink];
}
g<<dist[ul]<<' '<<costul;
return 0;
}