Консультация № 189555
06.06.2016, 11:46
0.00 руб.
06.06.2016, 12:25
0 2 0
Здравствуйте! Прошу помощи в следующем вопросе:

Код:
[code h=200]#include "stdafx.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <list>
#include <time.h>

using namespace std;

class graph
{
private:
vector <vector <int> > ad_list;
vector <vector <int> > ad_matr;
vector <vector <int> > matr_ves;
vector <vector <int> > bridges;
vector <vector <int> > block;
vector<int> bfs_res;
vector<int> bridge_list;
vector<int> point_list;

int n;
int t[100], f[100];
int timer = 0;
vector <int> comp;
void dfs1(int, bool*, int);
bool orgraph();
void show_vector(vector<vector<int> >);
void paint(int, int);
//bool cy(int v);
void cyclesSearch(int i, int &k, int &nZ, vector<int> &num, vector<int> &prev, vector<vector<int> > &masQ, vector<vector <int> > ad_list, vector<int> &tk);


public:

void comps();
void blocks();
bool org;
void dfs(int);
graph(int);
//void show_vector(vector<vector<int> >);
void bfs(int);
void bridge();
void child(int k);
void add_weight();
void cycles();
void show();
void kr(); //Для Крускала
void rnd_weight();

void Dxtr(int);

void pnt();





};



graph::graph(int k)
{
graph::n = k;
vector<int> tmp;
vector<int> tmp1;

const int a = 15, b = 34, c = 54, d = 6;
cout << "Параметры генерации" << endl << " A=" << a << " B="<<b << " C=" << c << " D=" <<d<<"Кол-во вершин "<<k<<endl;
for (int i = 0; i<k; i++)
{
tmp.clear();
tmp1.clear();
for (int j = 0; j<k; j++)
if ((((i*a + b*j) / c) % d) <= 1)
{
tmp1.push_back(1);
tmp.push_back(j);
}
else
tmp1.push_back(0);
ad_matr.push_back(tmp1);
ad_list.push_back(tmp);
}
org = orgraph();

};

void graph::kr()
{
rnd_weight();
int m = 0;
for (int i = 0; i<n; i++)
for (int j = 0; j<n; j++)
if (ad_matr[i][j] == 1) m++;
int k = 0;
vector<pair <int, pair<int, int> > > g(m);
for (int i = 0; i<n; i++)
for (int j = 0; j<n; j++)
if (matr_ves[i][j] >= 0)
{
g[k].second.first = i;
g[k].second.second = j;
g[k].first = matr_ves[i][j];
k++;
}
int cost = 0;
vector < pair<int, int> > res;
sort(g.begin(), g.end());
//for (int i=0;i<g.size();i++) cout<<g[i].second.first<<"->"<<g[i].second.second<<" = "<<g[i].first<<endl;
vector<int> tree_id(n);
for (int i = 0; i<n; ++i)
tree_id[i] = i;
int q = 0;
for (int i = 0; i<m; ++i)
{
int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
if (tree_id[a] != tree_id[b])
{
cost += l;
res.push_back(make_pair(a, b));
q++;
int old_id = tree_id[b], new_id = tree_id[a];
for (int j = 0; j<n; ++j)
if (tree_id[j] == old_id)
tree_id[j] = new_id;
}
}
cout << "Cost=" << cost << endl;
for (int i = 0; i<q; i++) cout << res[i].first << "->" << res[i].second << endl;
} //Крускал

bool graph::orgraph()
{
for (int i = 0; i<n; i++)
for (int j = 0; j<n; j++)
if (ad_matr[i][j] != ad_matr[j][i])
return true;
return false;
}

void graph::cycles()
{
int m = 0,
k = -1,
nZ = -1;

vector<int> num(n); //порядок обхода
vector<int> prev(n); //предки
vector<int> tk(n);
for (int i = 0; i < n; i++)
num[i] = prev[i] = tk[i] = -1;

for (int i = 0; i < n; i++)
m += ad_list[i].size();
m /= 2;
cout <<endl<< "Цикломатическое число =" << m << endl; //цикломатическое число(кол-во циклов короч)
vector<vector<int> > masQ(m - n + 2); //строка - цикл, в строке вершины цикла
cyclesSearch(0, k, nZ, num, prev, masQ, ad_list, tk);

//cout << "Количество циклов: " << (m - n + 2) << endl;
for (int i = 0; i < masQ.size(); i++)
{

for (int j = 0; j < masQ[i].size(); j++)
cout << masQ[i][j] << " -> ";
cout << endl;

}
}

void graph::cyclesSearch(int i, int &k, int &nZ, vector<int> &num, vector<int> &prev, vector<vector<int> > &masQ, vector<vector <int> > ad_list, vector<int> &tk)
{


num[i] = ++k;

for (int c = 0; c < ad_list[i].size(); c++)
{
int j = ad_list[i][c]; //adList - это список смежности
if (num[j] == -1)
{
prev[j] = i;
cyclesSearch(j, k, nZ, num, prev, masQ, ad_list, tk);
}
else
if ((org && (num[j]<num[i]) && (tk[j] == -1)) || (!org && ((prev[i] != j) && (num[i]>num[j]))))
{
nZ++;
int z = i;
while (z != j)
{
masQ[nZ].push_back(z);
z = prev[z];
}
masQ[nZ].push_back(j);
masQ[nZ].push_back(i);

}
}
tk[i] = k;

}

void graph::dfs1(int v, bool* used, int p = -1)
{

used[v] = true;
t[v] = f[v] = timer++;
int children = 0;
for (int i = 0; i<ad_list[v].size(); i++)
{

int to = ad_list[v][i];

if (to == p) continue;
if (!used[to])
{
dfs1(to, used, v);
f[v] = min(f[v], f[to]);
if (f[to]>t[v]) { vector<int> tmp; tmp.push_back(v); tmp.push_back(to); bridges.push_back(tmp); }
if ((f[to] >= t[v]) && (p != -1)) point_list.push_back(v);
children++;
}
if ((p == -1) && (children>1)) point_list.push_back(v);
else f[v] = min(f[v], t[to]);

}
comp.push_back(v);
};


void graph:: pnt()
{
point_list.clear();
bool * used = new bool[n];
for (int i=0; i<n; i++)
used[i]=false;
for(int i=0; i<n; ++i)
dfs1(i,used);
cout << "Точки разрыва" << endl;
for (int i=0; i<point_list.size(); i++)
cout<<point_list[i]<<" ";
cout<<endl;
}
void graph::comps()
{
bool *used = new bool[n];
for (int i = 0; i<n; i++) used[i] = false;
for (int i = 0; i<n; ++i)
if (!used[i])
{
comp.clear();
dfs1(i, used);
cout << "Компоненты связности :";
for (size_t j = 0; j<comp.size(); ++j)
cout << ' ' << comp[j];
cout << endl;
}
}

void graph::dfs(int v)
{
bool *used = new bool[n];
for (int i = 0; i<n; i++) used[i] = false;
dfs1(v, used);
};

void graph::show_vector(vector<vector<int> > ad_matr)
{
for_each(ad_matr.begin(), ad_matr.end(), [](vector<int>& tm)
{
for_each(tm.begin(), tm.end(), [](int i)
{
cout.width(2);
if (i<0) cout << "__ | "; else cout << i << " | ";
});
cout << endl;
});
cout << endl;

}
void graph::show()
{
cout << "Матрица смежности"<<endl;
for_each(ad_matr.begin(), ad_matr.end(), [](vector<int>& tm)
{
for_each(tm.begin(), tm.end(), [](int i)
{
cout << i << " ";
});
cout << endl;
});
cout << endl;

}

void graph::bfs(int v)
{
bfs_res.clear();
bool *used = new bool[n];
for (int i = 0; i<n; i++)
used[i] = false;
queue<int> q;
q.push(v);
used[v] = true;
while (!q.empty())
{
v = q.front();
q.pop();
bfs_res.push_back(v);
for (int i = 0; i<ad_list[v].size(); i++)
{
int w = ad_list[v][i];
if (used[w])
continue;
q.push(w);
used[w] = true;
}

}
cout << endl;
cout << "ПВШ" << endl;
for (int i = 0; i<bfs_res.size(); i++)
cout << bfs_res[i] << " ";
}

void graph::bridge()
{

timer = 0;
bridges.clear();
bool *used = new bool[n];
for (int i = 0; i<n; i++) used[i] = false;
for (int i = 0; i<n; i++) if (!used[i]) dfs1(i, used);
cout << "Мосты:" << endl;
show_vector(bridges);
}

void graph::child(int k)
{
point_list.clear();
bool *used = new bool[n];
for (int i = 0; i<n; i++) used[i] = false;
dfs1(k, used);
}

void graph::add_weight()
{
vector<int> tmp;
int a;
srand(time(NULL));
for (int i = 0; i<n; i++)
{

tmp.clear();
for (int j = 0; j<n; j++)
if (ad_matr[i][j] == 1)
{
//cout << "Enter weight: ";
//cin >> a;
a = rand() % 10 + 1;
tmp.push_back(a);
}
else
tmp.push_back(0);
matr_ves.push_back(tmp);
}

}

void graph::rnd_weight()
{
vector<int> tmp;
int a;
for (int i = 0; i<n; i++)
{
tmp.clear();
for (int j = 0; j<n; j++)
if (ad_matr[i][j] == 1) { a = rand() % 100; tmp.push_back(a); }
else tmp.push_back(-1);
matr_ves.push_back(tmp);
}
show_vector(matr_ves);

}

void graph::Dxtr(int st)
{
{
cout << "Алгоритм Дейкстры" << endl;
int V = n;
int count, index, i, u, m = st + 1;
int * distance = new int[V];
bool * visited = new bool[V];

for (i = 0; i<V; i++)
{
distance[i] = INT_MAX; visited[i] = false;
}
distance[st] = 0;
vector <int> sprint;
for (count = 0; count<V - 1; count++)
{
int min = INT_MAX;
for (i = 0; i<V; i++)
if (!visited[i] && distance[i] <= min)
{
min = distance[i]; index = i;
}
u = index;
visited[u] = true;
for (i = 0; i<V; i++)
if (!visited[i] && matr_ves[u][i] && distance[u] != INT_MAX &&
distance[u] + matr_ves[u][i]<distance[i])
distance[i] = distance[u] + matr_ves[u][i];
sprint.push_back(u);
}


cout << "Дистанции путей из вершины " << st << " \t\n";
for (i = 0; i<V; i++)
if (distance[i] != INT_MAX)
cout << m << " > " << i + 1 << " = " << distance[i] << endl;
else cout << m << " > " << i + 1 << " = " << "Недостижима" << endl;
for (int i = 0; i < sprint.size() - 1; i++)
cout << sprint[i] << " ";
}
cout << endl;

}



int main()
{

setlocale(LC_ALL, "Russian");
int points_count = 16;
graph k(points_count);
k.show();

k.pnt(); //Точки разрыва

k.bridge(); //Мосты

k.bfs(0); //ВПШ

k.cycles(); // Циклы

k.comps(); // Компоненты связности

k.add_weight(); // Матрица весов

for (size_t i = 0; i < points_count; i++)
k.Dxtr(i);

system("pause");
return 0;
}[/code]
Вопрос: почему с этими данными ошибка: const int a = 15, b = 34, c = 54, d = 6; проблема в этом:(d = 6)

и можете написать комментарии что и где происходит?

Обсуждение

давно
Посетитель
399158
228
06.06.2016, 11:53
общий
точнее за что каждая функция отвечает...
давно
Посетитель
399158
228
08.06.2016, 11:23
общий
никто не может?
Форма ответа