Pagini recente » Cod sursa (job #617294) | Cod sursa (job #938909) | Cod sursa (job #27808) | Cod sursa (job #2124724) | Cod sursa (job #1174721)
#include<fstream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 410
#define INF 100000.0
using namespace std;
ifstream f("adapost.in");
ofstream g("adapost.out");
int n,i,j,x,flux,nr,li,dest,ls,mij,sol,t[N],viz[N],cap[N][N],fl[N][N];
double cost,di[N][N],a[N*N],d[N];
struct punct{double x,y;}p[N],ad[N];
queue<int>q;
vector<pair<int,double> >v[N];
inline double dist(punct a,punct b){
return (double)sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));
}
inline bool bf(){
for(int i = 1 ; i <= dest ; ++ i)
d[i] = INF;
q.push(0);
viz[0] = 1;
d[0] = 0;
while(!q.empty())
{
x = q.front();
q.pop();
viz[x] = 0;
for(vector<pair<int,double> >::iterator it = v[x].begin() ; it != v[x].end() ; ++ it)
if(d[it->first] > d[x] + it->second && fl[x][it->first] < cap[x][it->first])
{
d[it->first] = d[x] + it->second;
t[it->first] = x;
if(!viz[it->first])
{
viz[it->first] = 1;
q.push(it->first);
}
}
}
return d[dest] != INF;
}
inline int fmcm(){
flux = 0;
cost = 0;
memset(fl,0,sizeof(fl));
while(bf())
{
x = dest;
while(x)
{
++ fl[t[x]][x];
-- fl[x][t[x]];
x = t[x];
}
cost += d[dest];
++ flux;
}
return flux;
}
inline bool verif(double x){
for(i = 1 ; i <= n ; ++ i)
v[i].clear();
for(i = 1 ; i <= n ; ++ i)
{
v[0].push_back(make_pair(i , 0));
cap[0][i] = 1;
v[i + n].push_back(make_pair(dest , 0));
cap[i + n][dest] = 1;
for(j = 1 ; j <= n ; ++ j)
if(di[i][j] <= x)
{
v[i].push_back(make_pair(n + j , di[i][j]));
v[n + j].push_back(make_pair(i , -di[i][j]));
cap[i][n + j] = 1;
}
}
if(fmcm() == n)
return 1;
return 0;
}
int main()
{
f >> n;
dest = n * 2 + 1;
for(i = 1 ; i <= n ; ++ i)
{
f >> p[i].x >> p[i].y ;
}
for(i = 1 ; i <= n ; ++ i)
{
f >> ad[i].x >> ad[i].y ;
}
for(i = 1 ; i <= n ; ++ i)
for(j = 1 ; j <= n ; ++ j)
di[i][j] = dist(p[i] , ad[j]),
a[++ nr] = di[i][j];
sort(a + 1 , a + nr + 1);
li = 1;
ls = nr;
while(li <= ls)
{
mij = (li + ls)>>1;
if(verif(a[mij]))
{
sol = mij;
ls = mij - 1;
}
else
li = mij + 1;
}
verif(a[sol]);
g << a[sol] << ' ' << cost << '\n';
return 0;
}