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

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

Восстановить пароль Регистрация
Другие темы раздела
C++ Пузырьковая сортировка http://www.cyberforum.ru/cpp-beginners/thread1186368.html
#include <iostream> #include <fstream> using namespace std; int main() { const int n = 5; int a; ifstream f("C:\\Users\\ÀÍÄÐÅÉ\\Desktop\\5 ÷èñåë.txt");
C++ Синхронизация семафорами+ общая память 3 потока. Синхронизация с помощью семафоров. Используется общая память. Вопрос состоит в том, как определить количество байт, нужных для выделения в общей памяти? Размер вектора у нас изменяется после инициализации указателя *a //verctor with our calculaded sums of equal elements //we`re finding our first&last max elements for rows and columns void calc_res_v (vector <int> v_res,const... http://www.cyberforum.ru/cpp-beginners/thread1186365.html
C++ Указатель this в конструкторе копирования
Добрый всем вечер. Подскажите пожалуйста, как правильно применить в конструкторе копирования указатель this? Вот есть код. Правильно ли тут применен этот указатель? #include "stdafx.h" #include <iostream> using namespace std;
C++ Определить симметричность матрицы испльзуя указатели
Задание, определить симметричность матрицы с помощью указателей. Не могу никак разобраться с указателями, но что-то написала (просьба не смеяться:) ) Меня интересует как обратится к элементам матрицы что бы сравнить их. p.s. Программа не работает, все время пишет что матрица симметрична. #include <iostream> #include <conio.h> using namespace std; int main()
C++ Во время футбольной игры формируется файл, распечатать фамилии 3 самых результативных игроков команды http://www.cyberforum.ru/cpp-beginners/thread1186339.html
Во время футбольной игры формируется файл, который включает фамилию игрока и количество набранных за игру очков. Используя сформированный файл, распечатать фамилии 3 самых результативных игроков команды. Вот запись в файл #include <stdio.h> #include <string.h> #define N 4 struct swed { char fio; int bal;
C++ DES в режиме ECB Вообщем такая проблема реализовал DES в режиме ECB,но что не хочет расшифровывать ,уже не знаю голову сломал,помогите найти ошибку а то уже курсовую сдавать а у меня нет // ConsoleApplication17.cpp: определяет точку входа для консольного приложения. // #include "stdafx.h" #include <iostream> #include <fstream> #include <string> #include <stdio.h> подробнее

Показать сообщение отдельно
vasyakolodov
0 / 0 / 0
Регистрация: 17.12.2013
Сообщений: 5
24.05.2014, 01:11     Максимальный поток минимальной стоимости
Вечер добрый, нашел программу работает, выдает как я понял максимальный поток и минимальную стоимость. Вопрос в следующем, как там матрица пропускных способностей задается? И если не сложно поясните код пожалуйста.
C++ (Qt)
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;
 }
Добавлено через 2 минуты
или просто разобранный пример, что там и как происходит? буду признателен!
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 22:44. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru