Форум программистов, компьютерный форум CyberForum.ru

Максимальный поток минимальной стоимости - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ В матрице найти максимальный и минимальный элементы. http://www.cyberforum.ru/cpp-beginners/thread737988.html
В заданной матрице A размером найти максимальный и минимальный элементы и переставить столбцы и строки, на пересечении которых находятся данные элементы.
C++ Упаковка массива данных float с заданной точностью Есть интересная задачка, если она не подходит для начинающих пересоздам тему у экспертов. Задача вроде бы типовая на вид, но ничего подобного так и не удалось найти(возможно не там искал). Вкратце, задан массив float и требуемая точность. Надо рассчитать, сколько бит нужно для этой точности и сделать последовательность, где каждый float упакован в это кол-во бит. Более формально: Задан... http://www.cyberforum.ru/cpp-beginners/thread737987.html
C++ Найти сумму ряда с точностью до члена ряда
Найти сумму ряда с точностью до члена ряда, меньшего 0.0001 для заданного значения и сравнить эту сумму с функцией контроля. Для вычисления последующего значения члена ряда использовать рекуррентную формулу.
Вычислить значение функции (ошибка в условии) C++
Hi! Вычислить значение функции: #include "stdafx.h" #include <iostream> #include <math.h> #include <conio.h> using namespace std; void main()
C++ при переходе в функцию происходит ошибка http://www.cyberforum.ru/cpp-beginners/thread737969.html
Программа арифметики длинных чисел... Ошибка возникает, если в меню выбрать "Умножение"... Вооот... #include <iostream> #include <string> using namespace std;
C++ Найти максимальное четное число, стоящее над главной диагональю матрицы Дана матрица (в первой строке - количество строк и столбцов, в след строке элементы матрицы). Найти максимальное четное число, стоящее над главной диагональю. Если над главной диагональю нет четных чисел, вывести 'Нет' что с этим делать?! Час уже мучаюсь.... подробнее

Показать сообщение отдельно
c++\noob
-2 / 2 / 0
Регистрация: 13.11.2010
Сообщений: 52

Максимальный поток минимальной стоимости - C++

19.12.2012, 10:26. Просмотров 1119. Ответов 0
Метки (Все метки)

Нужно реализовать алгоритм нахождения максимального потока минимальной стоимости в сети.Нашёл в интернете код программы, но не могу разобраться в нём насчёт переменных..Может кто-нибудь поможет с этим или у кого-то завалялась подобная программка. Буду очень признателен!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <queue>
#include <vector>
#include <climits>
#include <iostream>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const int maxnodes = 200000;
 
int nodes = maxnodes;
int prio[maxnodes], curflow[maxnodes], prevedge[maxnodes], prevnode[maxnodes], q[maxnodes], pot[maxnodes];
bool inqueue[maxnodes];
 
struct Edge {
  int to, f, cap, cost, rev;
};
 
vector<Edge> graph[maxnodes];
 
void addEdge(int s, int t, int cap, int cost) {
  Edge a = {t, 0, cap, cost, graph[t].size()};
  Edge b = {s, 0, 0, -cost, graph[s].size()};
  graph[s].push_back(a);
  graph[t].push_back(b);
}
 
void bellmanFord(int s, int dist[]) {
  fill(dist, dist + nodes, INT_MAX);
  dist[s] = 0;
  int qt = 0;
  q[qt++] = s;
  for (int qh = 0; (qh - qt) % nodes != 0; qh++) {
    int u = q[qh % nodes];
    inqueue[u] = false;
    for (int i = 0; i < (int) graph[u].size(); i++) {
      Edge &e = graph[u][i];
      if (e.cap <= e.f) continue;
      int v = e.to;
      int ndist = dist[u] + e.cost;
      if (dist[v] > ndist) {
        dist[v] = ndist;
        if (!inqueue[v]) {
          inqueue[v] = true;
          q[qt++ % nodes] = v;
        }
      }
    }
  }
}
 
pii minCostFlow(int s, int t, int maxf) {
// bellmanFord can be safely commented if edges costs are non-negative
  bellmanFord(s, pot);
  int flow = 0;
  int flowCost = 0;
  while (flow < maxf) {
    priority_queue<ll, vector<ll>, greater<ll> > q;
    q.push(s);
    fill(prio, prio + nodes, INT_MAX);
    prio[s] = 0;
    curflow[s] = INT_MAX;
    while (!q.empty()) {
      ll cur = q.top();
      int d = cur >> 32;
      int u = cur;
      q.pop();
      if (d != prio[u])
        continue;
      for (int i = 0; i < (int) graph[u].size(); i++) {
        Edge &e = graph[u][i];
        int v = e.to;
        if (e.cap <= e.f) continue;
        int nprio = prio[u] + e.cost + pot[u] - pot[v];
        if (prio[v] > nprio) {
          prio[v] = nprio;
          q.push(((ll) nprio << 32) + v);
          prevnode[v] = u;
          prevedge[v] = i;
          curflow[v] = min(curflow[u], e.cap - e.f);
        }
      }
    }
    if (prio[t] == INT_MAX)
      break;
    for (int i = 0; i < nodes; i++)
      pot[i] += prio[i];
    int df = min(curflow[t], maxf - flow);
    flow += df;
    for (int v = t; v != s; v = prevnode[v]) {
      Edge &e = graph[prevnode[v]][prevedge[v]];
      e.f += df;
      graph[v][e.rev].f -= df;
      flowCost += df * e.cost;
    }
  }
  return make_pair(flow, flowCost);
}
 
// Usage example
 
int main() {
  int capacity[3][3] = {
    { 0, 3, 2},
    { 0, 0, 2},
    { 0, 0, 0}
  };
  nodes = 3;
  for (int i = 0; i < nodes; i++)
    for (int j = 0; j < nodes; j++)
      if (capacity[i][j] != 0)
        addEdge(i, j, capacity[i][j], 1);
  int s = 0;
  int t = 2;
  pii res = minCostFlow(s, t, INT_MAX);
  int flow = res.first;
  int flowCost = res.second;
  cout << (4 == flow) << endl;
  cout << (6 == flowCost) << endl;
}
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru