Pagini recente » Cod sursa (job #35039) | Monitorul de evaluare | Cod sursa (job #3296295) | Cod sursa (job #3040794) | Cod sursa (job #1015737)
#include <fstream>
#include <utility>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define N 1000
#define oo 0x3f3f3f3f
using namespace std;
typedef struct{
double x, y;
} elem;
elem Ad[N], Sold[N];
bool inq[N], viz[N];
int flux, step, n;
double Cost[N][N], Dist[N], sol, cost;
int C[N][N], S, D, prec[N];
queue<int>Q;
vector<pair<double, pair<int, int> > >distances;
vector<int>G[N];
int nd;
bool cmp(pair<double, pair<int, int> > x, pair<double, pair<int, int> > y)
{
return x.first < y.first;
}
double get_dist(elem a, elem b)
{
double x = (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
x = sqrt((double)x);
return x;
}
bool Bellman(double val)
{
vector<int> :: iterator it;
int i, x;
for(i = S; i <= D; i++) Dist[i] = oo;
Dist[S] = 0;
Q.push(S);
while(!Q.empty())
{
x = Q.front(); Q.pop();
inq[x] = 0;
for(it = G[x].begin(); it != G[x].end(); it++)
if(C[x][*it] and Dist[*it] > Dist[x] + Cost[x][*it])
{
Dist[*it] = Dist[x] + Cost[x][*it];
prec[*it] = x;
if(!inq[*it])
{
inq[*it] = 1;
Q.push(*it);
}
}
}
return Dist[D] != oo;
}
bool BF(double val)
{
vector<int> :: iterator it;
int x, i;
memset(viz, 0, sizeof(viz));
Q.push(S);
viz[S] = 1;
while(!Q.empty())
{
x = Q.front();
Q.pop();
for(it = G[x].begin(); it != G[x].end(); it++)
if(C[x][*it] and Cost[x][*it] <= val and !viz[*it])
{
viz[*it] = 1;
prec[*it] = x;
Q.push(*it);
}
}
return viz[D];
}
bool not_good(double val)
{
int i;
while(BF(val))
{
for(i = D; i != S; i = prec[i])
C[prec[i]][i]--, C[i][prec[i]]++;
flux++;
}
return flux < n;
}
int main()
{
int i, j, x, y;
//double x, y;
ifstream fi("adapost.in");
ofstream fo("adapost.out");
fi >> n;
S = 0; D = 2*n+1;
for(i = 1; i <= n; i++)
{
fi >> Sold[i].x >> Sold[i].y;
}
for(i = 1; i <= n; i++)
{
fi >> Ad[i].x >> Ad[i].y;
}
for(i = 1; i <= n; i++) { G[S].push_back(i); G[i].push_back(S); }
for(j = 1; j <= n; j++) { G[D].push_back(j+n); G[j+n].push_back(D); }
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
Cost[i][j+n] = get_dist(Sold[i], Ad[j]);
Cost[j+n][i] = -Cost[i][j+n];
distances.push_back(make_pair(Cost[i][j+n], make_pair(i, j+n)));
C[i][j+n] = 1;
C[S][i] = 1;
C[j+n][D] = 1;
}
nd = distances.size();
sort(distances.begin(), distances.end(), cmp);
for(i = 0; i < nd; i++)
{
x = distances[i].second.first;
y = distances[i].second.second;
G[x].push_back(y); G[y].push_back(x);
if(!not_good(distances[i].first))
{
sol = distances[i].first;
break;
}
}
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
{
C[i][j+n] = 1;
C[j+n][i] = 0;
C[S][i] = 1;
C[i][S] = 0;
C[i][S] = 0;
C[j+n][D] = 1;
C[D][j+n] = 0;
}
while(Bellman(sol))
{
for(i = D; i != S; i = prec[i])
C[prec[i]][i]--, C[i][prec[i]]++;
cost += Dist[D];
}
fo << setprecision(5) << fixed;
fo << sol << " " << cost << "\n";
return 0;
}