Pagini recente » Cod sursa (job #1192758) | Cod sursa (job #2562901) | Cod sursa (job #283871) | Cod sursa (job #3178159) | Cod sursa (job #422652)
Cod sursa(job #422652)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <math.h>
#include <iomanip>
using namespace std;
#define INF 0x3f3f3f3f
vector<int> G[401];
vector<pair<int, double> > V[805];
int TT[805], C[805][805], F[805][805];
int N, L[401], R[401], U[401];
double D[401][401], sol, dist;
double val[401*401], Di[805];;
struct Coord {
double x, y;
} S[401], A[401];
int pairUp(int nod) {
if(U[nod]) return 0;
U[nod]=1;
for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
if(!R[(*it)]) {
L[nod]=(*it);
R[(*it)]=nod;
return 1;
}
}
for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
if(pairUp(R[(*it)])) {
L[nod]=(*it);
R[(*it)]=nod;
return 1;
}
}
return 0;
}
int Verifica(double d) {
int i, j;
for(i=1; i<=N; i++) {
G[i].clear(); R[i]=L[i]=0;
}
for(i=1; i<=N; i++) {
for(j=1; j<=N; j++) {
if(D[i][j]<=d) { G[i].push_back(j); }
}
}
int ok=1;
while(ok) {
memset(U, 0, sizeof(U));
ok=0;
for(i=1; i<=N; i++) {
if(!L[i]) {
if(pairUp(i)) { ok=1; }
}
}
}
for(i=1; i<=N; i++) {
if(!L[i]) { return 0; }
}
return 1;
}
struct cmp {
bool operator()(const int &a, const int &b) {
return Di[a]>Di[b];
}
};
double BellmanFord() {
int i, j, p, q;
priority_queue <int, vector <int>, cmp > Q;
bool InQueue[805];
for(i=0; i<=2*N+2; i++) {
Di[i]=INF; InQueue[i]=0;
TT[i]=-1;
}
Di[1]=0; InQueue[1]=1;
Q.push(1);
while(!Q.empty()) {
p=Q.top(); Q.pop(); InQueue[p]=0;
for(vector<pair<int, double> >::iterator it=V[p].begin(); it!=V[p].end(); it++) {
if(C[p][(*it).first]>F[p][(*it).first] && Di[p]+(*it).second<Di[(*it).first]) {
Di[(*it).first]=Di[p]+(*it).second;
TT[(*it).first]=p;
if(!InQueue[(*it).first]) {
InQueue[(*it).first]=1;
Q.push((*it).first);
}
}
}
}
if(Di[2*N+2]<INF) {
int fmin=INF;
for(i=2*N+2; i!=1; i=TT[i]) {
fmin=min(fmin, C[TT[i]][i]-F[TT[i]][i]);
}
for(i=2*N+2; i!=1; i=TT[i]) {
F[TT[i]][i]+=fmin;
F[i][TT[i]]-=fmin;
}
return (double)Di[2*N+2]*fmin;
}
return 0;
}
int main() {
fstream f1, f2;
int i, j, p, q, nr=0;
f1.open("adapost.in", ios::in);
f1>>N;
for(i=1; i<=N; i++) {
f1>>S[i].x>>S[i].y;
}
for(i=1; i<=N; i++) {
f1>>A[i].x>>A[i].y;
}
for(i=1; i<=N; i++) {
for(j=1; j<=N; j++) {
//distana de la soldatul i la adapostul j
D[i][j]=(double)(A[j].x-S[i].x)*(A[j].x-S[i].x)+(double)(A[j].y-S[i].y)*(A[j].y-S[i].y);
D[i][j]=sqrt(D[i][j]);
val[nr]=D[i][j]; nr++;
}
}
sort(val, val+nr);
int ls=0, ld=nr-1;
while(ls<=ld) {
int mij=(ls+ld)>>1;
double LDS=(double)val[mij];
if(Verifica(LDS)) {
sol=LDS;
ld=mij-1;
}
else {
ls=mij+1;
}
}
//construiesc graful pentru flux maxim de cost minim
for(i=1; i<=N; i++) {
for(j=1; j<=N; j++) {
if(D[i][j]<=sol) {
double asd=D[i][j];
V[i+1].push_back(make_pair(N+1+j, asd));
V[N+1+j].push_back(make_pair(i+1, -asd));
C[i+1][N+1+j]=1;
}
}
}
for(i=2; i<=N+1; i++) {
V[1].push_back(make_pair(i, 0));
V[i].push_back(make_pair(1, 0));
C[1][i]=1;
}
for(i=N+2; i<=2*N+1; i++) {
V[i].push_back(make_pair(2*N+2, 0));
V[2*N+2].push_back(make_pair(i, 0));
C[i][2*N+2]=1;
}
//fac flux maxim de cost minim de la sursa 1 la destinatia 2*N+2
double flow=0, f=1;
while(f) {
f=BellmanFord();
flow+=f;
}
f2.open("adapost.out", ios::out);
f2<<setprecision(10)<<sol<<" "<<flow<<endl;
f1.close(); f2.close();
return 0;
}