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

Вывод пути (алгоритм Дейкстры) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Winsock C++ клиент - сервер http://www.cyberforum.ru/cpp-beginners/thread1198387.html
#include <winsock2.h> // сервер #include <iostream> using namespace std; int main(){ // инициализация winsock WSADATA WSAData; if (WSAStartup (MAKEWORD(1,1), &WSAData)!=0) { cout << "WSAStartup faild. Error:" << WSAGetLastError();
C++ Сравнение дат, не работает функция Ребят, помогите пожалуйста исправить функцию. Я должна сделать программу с таким заданием: Создать класс Triad (тройка чисел); определить метод сравнения триад. Определить производный класс Date с полями: год, месяц и день. Определить полный набор методов сравнения дат. Моя программа правильно работает, что касается с числами. Но последнюю функцию(сравнение дат) она не выполняет. :(... http://www.cyberforum.ru/cpp-beginners/thread1198381.html
Генерация псевослучайных чисел (метод Неймана) C++
Как задать цикл, что 100 цифр. Задаётся число и отбрасывает 2 последние цифры, и дальше с новым числом работать и так 100 раз. Помогите
C++ Заполнить матрицу по заданному образцу
Здравствуйте. Помогите пожалуйста с задачей, уже несколько дней сижу,ничего не получается. Задано число N(может быть четным или нечетным). Заполнить элементы массива по заданному образцу. То есть нужен некоторый алгоритм который заполняет элементы массива по особенному , после того как введем число N с клавиатуры Найти несколько вариантов и найти самый быстрый. образец: при вводе N=5...
C++ Многопоточность, выход из бесконечного цикла c++11 http://www.cyberforum.ru/cpp-beginners/thread1198343.html
Всем привет. Я в задачах многопоточности - новичок (начал ей заниматься буквально несколько часов назад), инфу искал, читал, но как-то пока не помогает. Столкнулся с задачей (с++11 std::thread) код не оригинальный, а упрощённый, чтобы показать саму суть, подразумевается, что все необходимые include'ы уже есть. есть class SomeClass { private: bool _stopCycle;
C++ Вычислите сумму элементов целочисленной матрицы, ниже побочной диагонали Дана целочисленная матрица. Вычислите сумму элементов матрицы, ниже побочной диагонали. Выведите на экран исходный массив и результат вычисления. подробнее

Показать сообщение отдельно
iliya785
23 / 23 / 8
Регистрация: 04.06.2014
Сообщений: 80
05.06.2014, 02:11     Вывод пути (алгоритм Дейкстры)
Кинул уже на почту . Но скину вдруг кому пригадится
Алгоритм Крускала
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
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
 
struct edge{
    int a,b,c;
};
 
vector <int> parent(100001);
vector <edge> q(100001);
long long ans = 0;
 
bool cmp(edge a,edge b){
    return a.c < b.c;
}
 
int find_set(int v){
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}
 
void union_sets(int a,int b,int c){
    a = find_set(a);
    b = find_set(b);
    if (a != b){
        parent[b] = a;
        ans += c;
    }
}
 
int main(){
    int n;
    scanf("%d",&n);
    for (int i=1;i<=n;++i)
        parent[i] = i;
    int m = -1,x;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j){
                scanf("%d",&x);
                if (x){
                    q[++m].a = i;
                    q[m].b = j;
                    q[m].c = x;
                }
        }
    sort(q.begin(),q.begin()+m,cmp);
    for (int i=0;i<m;++i)
        union_sets(q[i].a,q[i].b,q[i].c);
    printf("%d\n",ans);
}
P.S. Только измени название темы

Добавлено через 43 секунды
Алгоритм Флойда
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
 
int main(){
    cin.sync_with_stdio(false);
    int n;
    cin>>n;
    int w[n][n];
    for (int i=0;i<n;++i)
        for (int j=0;j<n;++j){
            cin>>w[i][j];
            if (!w[i][j])   w[i][j] = 1000*1000*1000;
        }
    for (int k=0;k<n;++k)
        for (int i=0;i<n;++i)
            for (int j=0;j<n;++j)
                w[i][j] = min(w[i][j],w[i][k] + w[k][j]);
    for(int i=0;i<n;++i)
        w[i][i] = 0;
    int l,r;
    cin>>l>>r;
    cout<<w[--l][--r]<<endl;
}
Добавлено через 54 секунды
Форда-Фалкерсона(max поток)
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
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
 
const int inf = 1000*1000*1000;
 
int main(){
    int n,m,u,v,w,s,t;
    scanf("%d%d",&n,&m);
    int c[11][11],f[11][11];
    for (int i=1;i<=n;++i)
        for (int j=1;j<=n;++j)
            c[i][j] = f[i][j] = 0;
    for (int i=0;i<m;++i){
        scanf("%d%d%d",&u,&v,&w);
        c[u][v] = w;
    }
    scanf("%d%d",&s,&t);
    for (;;){
        vector < int > p(11),cf(11);
        queue < int > q;
        q.push(s); cf[s] = inf;
        while (!q.empty()){
            int v = q.front();
            for (int i=1;i<=n;++i){
                if (!p[i] && c[v][i] - f[v][i] > 0){
                    q.push(i);
                    p[i] = v;
                    cf[i] = min(cf[v],c[v][i] - f[v][i]);
                }
            }
            q.pop();
        }
        if (!p[t])  break;
        for (int u=t;u != s;u = p[u]){
            f[p[u]][u] += cf[t];
            f[u][p[u]] -= cf[t];
        }
    }
    long long flow = 0;
    for (int i=1;i<=n;++i)
        if (c[s][i] > 0)
            flow += f[s][i];
    printf("%d\n",flow);
}
 
Текущее время: 03:55. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru