Pagini recente » Cod sursa (job #909899) | Cod sursa (job #62610) | Cod sursa (job #1203557) | Cod sursa (job #2692223) | Cod sursa (job #681361)
Cod sursa(job #681361)
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
#define NMAx 810
#define oo (1<<30)
#define pb push_back
#define dist(a,b,c,d) sqrt((a-b)*(a-b)+(c-d)*(c-d))
using namespace std;
vector <int> G[NMAx];
queue <int> Q;
int n,S,D,color,inQ[NMAx],tata[NMAx];
double sol,Cost[NMAx][NMAx],dist[NMAx];
double X[NMAx],Y[NMAx];
bool Flux[NMAx][NMAx];
bool BF() {
int i,nod,vecin;
for(i=S;i<=D;i++)
dist[i]=oo;
dist[S]=0;
Q.push(S);
color++;
while(!Q.empty()) {
nod=Q.front();
Q.pop();
inQ[nod]=false;
for(i=0;i<G[nod].size();i++) {
vecin=G[nod][i];
if(Flux[nod][vecin]>0&&dist[vecin]>dist[nod]+Cost[nod][vecin]) {
dist[vecin]=dist[nod]+Cost[nod][vecin];
tata[vecin]=nod;
if(inQ[nod]!=color) {
Q.push(vecin);
inQ[vecin]=color;
}
}
}
}
if(dist[D]==oo)
return 0;
return 1;
}
void bulid_flow_network() {
int i,j;
double d;
S=0;
D=2*n+1;
for(i=1;i<=n;i++) {
G[S].pb(i);
Flux[S][i]=1;
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++) {
d=dist(X[i],X[j],Y[i],Y[j]);
G[i].pb(j);
Flux[i][j]=1;
Cost[i][j]=d;
G[j].pb(i);
Cost[j][i]=-d;
}
for(i=n+1;i<=2*n;i++) {
G[i].pb(D);
Flux[i][D]=1;
}
}
void citire() {
ifstream in("adapost.in");
in>>n;
for(int i=1;i<=2*n;i++)
in>>X[i]>>Y[i];
in.close();
}
void afis() {
int i,j;
double e=0;
ofstream out("adapost.out");
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(!Flux[i][j])
e=max(e,Cost[i][j]);
out<<fixed<<setprecision(5)<<e<<' ';
out<<fixed<<setprecision(5)<<sol<<'\n';
out.close();
}
int main() {
int flow,nod;
citire();
bulid_flow_network();
while(BF()) {
flow=oo;
for(nod=D;nod!=S;nod=tata[nod])
flow=min(flow,(int)Flux[tata[nod]][nod]);
for(nod=D;nod!=S;nod=tata[nod]) {
Flux[tata[nod]][nod]-=flow;
Flux[nod][tata[nod]]+=flow;
}
sol+=dist[D];
}
afis();
return 0;
}