Bella at 20:14, 26 November 2018

2018-11-26T20:14:13Z

New page

<syntaxhighlight>
// Solutie Flux
// Tinca Matei
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 8;
int x[2*MAX_N], y[2*MAX_N];
int num[2*MAX_N];

// Clasa de flux maxim de cost minim
class MinCostMaxFlow {
int n, src, dest;

// Lista de adiacenta
vector<int> graph[1+2*MAX_N+1];

// Capacitatile pe fiecare muchie
int kappa[1+2*MAX_N+1][1+2*MAX_N+1];

// Fluxul transmis pe fiecare muchie
int flow[1+2*MAX_N+1][1+2*MAX_N+1];

// Parintele unui nod in arborele de la Bellman-Ford
int papa[1+2*MAX_N+1];

// costul unei muchii din graf
double cost[1+2*MAX_N+1][1+2*MAX_N+1];

// Cel mai bun cost de la sursa pana la nodul curent
double bestcost[1+2*MAX_N+1];

// Pompeaza flux de la sursa la destinatie pe drumul in arborele de la Bellman-Ford
void pump(int nod) {
int i = nod;
int fl = 10;
// Initial trebuie sa calculam cat flux pompam pe drumul respectiv
while(i != src) {
fl = min(fl, kappa[papa[i]][i] - flow[papa[i]][i]);
i = papa[i];
}

// Pompam fluxul propriu-zis pe drumul din arborele Bellman-Ford
while(nod != 0) {
flow[papa[nod]][nod] += fl;
flow[nod][papa[nod]] -= fl;
nod = papa[nod];
}

// Reactualizam cantitatea pompata de flux in total si costul in total
maxfl += fl;
mincost += bestcost[dest] * fl;
}

// Baga Bellman-Ford; returneaza true daca a gasit un drum pe care poate pompa flux de la sursa la destinatie
bool bellmanford() {
deque<pair<int, double> > q;

// Initializam toate costurile cu infinit, in afara de costul sursei care va fi 0
for(int i = 0; i < n; ++i)
bestcost[i] = 1000000000.0f;
bestcost[src] = 0.0f;

// Bagam sursa in coada
q.push_back(make_pair(src, 0.0f));

while(!q.empty()) {
// Scoatem primul element din coada
int nod = q.front().first;
double costnod = q.front().second;
q.pop_front();

// Reactualizam costurile minime pt fiecare vecin
for(auto it: graph[nod]) {
if(flow[nod][it] < kappa[nod][it] && bestcost[nod] + cost[nod][it] < bestcost[it]) {
bestcost[it] = bestcost[nod] + cost[nod][it];
q.push_back(make_pair(it, bestcost[it]));
papa[it] = nod;
}
}
}

// Exista drum de la sursa pana la destinatie
if(bestcost[dest] < 1000000000.0f) {
pump(dest);
return true;
}
return false;
}

public:
int maxfl;
double mincost;

// Initializeaza toate variabilele interne
MinCostMaxFlow(int _n) {
n = _n;
src = 0;
dest = n - 1;
maxfl = mincost = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
kappa[i][j] = flow[i][j] = cost[i][j] = 0;
}

// Adauga o muchie de la nodul a la nodul b cu capacitate k si cost c
void pushEdge(int a, int b, int k, double c) {
graph[a].push_back(b);
graph[b].push_back(a);
cost[a][b] = c;
cost[b][a] = -c;
kappa[a][b] = k;
}

// Ruleaza algoritmul de flux
void runFlow() {
while(bellmanford());
}
};

// Returneaza patratul lui x
double sqr(double x) {
return x * x;
}

// Returneaza distanta dintre doua puncte (x1, y1), (x2, y2)
double dist(double x1, double y1, double x2, double y2) {
return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

int main() {
int n;
double rez = 1000000000.0f;

// Citirea numerelor
FILE *fin = fopen("xd.in", "r");
fscanf(fin, "%d", &n);
for(int i = 0; i < 2 * n; ++i)
fscanf(fin, "%d%d", &x[i], &y[i]);
fclose(fin);

// Impart toate casele in doua submultimi. Intre doua case din submultimi diferite
// adaug o muchie de capacitate 1 si cost egal cu distanta dintre cele doua puncte
for(int i = 0; i < (1 << (2 * n)); ++i) {
int cnt = 0;
// Renumerotam toate casele; Cele din multimea A vor fi numerotate de la 1 pana la n,
// iar cele din multimea B vor fi numerotate de la n + 1 pana la 2 * n
for(int j = 0; j < 2 * n; ++j)
if((1 << j) & i) {
cnt++;
num[j] = cnt;
} else
num[j] = n + (j + 1) - cnt;

if(cnt == n) {
MinCostMaxFlow flx(2 * n + 2);

// Construirea propriu-zisa a grafului
for(int a = 0; a < 2 * n; ++a) {
for(int b = 0; b < 2 * n; ++b)
if(((1 << a) & i) > 0 && ((1 << b) & i) == 0)
flx.pushEdge(num[a], num[b], 1, dist(x[a], y[a], x[b], y[b]));

// Adaug o muchie de la sursa la fiecare nod din multimea A
if((1 << a) & i)
flx.pushEdge(0, num[a], 1, 0);
else // Adaug o muchie de la fiecare nod din multimea B la destinatie
flx.pushEdge(num[a], 2 * n + 1, 1, 0);
}

// Rulez fluxul pe graful construit
flx.runFlow();

// In graful construit, cuplajul trebuie sa fie perfect!!!
assert(flx.maxfl == n);

// reactualizam rezultatul
rez = min(rez, flx.mincost);
}
}

// Afisam rezultatele
FILE *fout = fopen("xd.out", "w");
fprintf(fout, "%.10f", rez);
fclose(fout);
return 0;
}

/*

Graful construit:

Noi ne construim un graf bipartit format din doua multimi A si B. Noi vrem sa cuplam fiecare nod din multimea A cu un nod din multimea B
Costul unei muchii dintre A si B va fi distanta dintre cele doua puncte pe care le reprezinta.

Algoritmul de cuplaj maxim de cost minim se implementeaza cu ajutorul algoritmului de flux maxim de cost minim

Avem sursa(0) si destinatia(2*n+1) si nodurile interne (cele din multimea A(1...N) si cele din multimea B(N+1...2N))
Intre sursa si fiecare nod din multimea A avem o muchie de capacitate 1 si cost 0
Intre fiecare nod din multimea B si destinatie avem o muchie de capacitate 1 si cost 0
Intre fiecare nod din multimea A si multimea B avem o muchie de capacitate 1 si cost egal cu distanta dintre cele doua puncte

Capacitatile de la ultimul tip de muchii nu este asa de relevant, acesta poate fi infinita, atata timp cat este mai mare decat 1.
Celalalte muchii trebuie sa aiba capacitate neaparat 1

*/

</syntaxhighlight>

Tmp isa - Revision history

Bella at 20:14, 26 November 2018