Pagini recente » Cod sursa (job #1346251) | Cod sursa (job #884482) | Cod sursa (job #2222028) | Cod sursa (job #2268524) | Cod sursa (job #422630)
Cod sursa(job #422630)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <math.h>
using namespace std;
#define INF 999999999
vector<int> G[401];
vector<pair<int, long long> > 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;
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;
}
int BellmanFord() {
int i, j, p, q;
queue<int> Q;
long long Di[805];
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.front(); Q.pop(); InQueue[p]=0;
for(vector<pair<int, long long> >::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 Di[2*N+2]*fmin;
}
return 0;
}
int main() {
FILE *f1=fopen("adapost.in", "r");
fstream f2;
int i, j, p, q;
fscanf(f1, "%d", &N);
for(i=1; i<=N; i++) {
fscanf(f1, "%lf%lf", &S[i].x, &S[i].y);
}
for(i=1; i<=N; i++) {
fscanf(f1, "%lf%lf", &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]);
}
}
int ls=1, ld=1000000;
while(ls<=ld) {
int mij=(ls+ld)>>1;
double LDS=(double)mij/1000;
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) {
long long asd=(long long)(D[i][j]*100000);
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
long long flow=0, f=1;
while(f) {
f=BellmanFord();
flow+=f;
}
f2.open("adapost.out", ios::out);
f2<<sol<<" "<<(long double)flow/100000<<endl;
fclose(f1); f2.close();
return 0;
}