Как уменьшить ключ для определенного ребра в priority_queue & lt; PI, vector & lt; PI & gt; , Больше & л; PI & GT; & gt; пытается реализовать алгоритм prim?

Есть три способа, которые я знаю.

1. Если вы настаиваете на использовании стандартной библиотеки priority_queueВы можете вставить каждую вершину несколько раз, но игнорируйте ее каждый раз, когда видите ее, кроме первой. В своем коде вы можете изменить if(vis[i]!=1) w=w+pp.top().ff; в if(vis[i]==1) continue; (возможно, не проверял). Недостатком является то, что ваш priority_queue может вырасти до O (| E |) памяти.

2. Вы также можете использовать стандартные библиотеки set вместо priority_queue, Затем, когда вы хотите вставить пару (distance, vertex)сначала нужно найти и удалить пару (old_distance, vertex) если это в наборе. Знать old_distance для каждого vertex Вы всегда должны поддерживать массив (или вектор) с текущими расстояниями. Таким образом, вы сохраняете память на O (| V |), но set имеет больший постоянный коэффициент, чем priority_queue,

3. Наконец, вы можете реализовать приоритетную очередь, которая позволяет удалять. Допустим, вы реализуете приоритетную очередь в виде двоичной кучи. Затем вам нужно будет поддерживать обратную перестановку элементов в очереди с приоритетами: для каждого элемента v, хранить и отслеживать текущий индекс кучи v, Один из другие ответы похоже, что он реализует этот подход, обратная перестановка index_map,

priority_queue в C ++ не предоставляет функциональность операции уменьшения ключа, что означает, что мы не можем найти ключ в priority_queue и уменьшить его значение. Один из способов, которым я знаю, чтобы достичь этого, состоит в том, чтобы реализовать очередь приоритетов самостоятельно, а затем поддерживать другую структуру ( vector или map) который будет хранить индексы ключей в очереди приоритетов. Попытайтесь понять код ниже, который использует эту идею.

// C++11 code
#include <iostream>
#include <vector>
#include <cstring>
#define SIZE 5          // number of vertices.
#define INF 100000000

/* This vector will contain a pair of integers where the first integer in
the pair is value(cost) and the second is the vertex.
This will be our priority queue.
*/
std::vector <std::pair <int, int> > pq (SIZE);
int size = SIZE;        // size of priority queue
int index_map[SIZE];

// Shift up the key with lower value.
void sift_up(int index) {
int parent = (index-1)/2;
while(index >= 0 && pq[index].first < pq[parent].first) {
index_map[pq[index].second] = parent;
index_map[pq[parent].second] = index;
std::swap(pq[index], pq[parent]);
index = parent;
parent = (index - 1)/2;
}
}

// Shift down the key with higher value.
void sift_down(int index) {
int left = 2*index+1, right = 2*index+2;
int min_index = index;
if(left < size && pq[left].first < pq[min_index].first)
min_index = left;
if(right < size && pq[right].first < pq[min_index].first)
min_index = right;
if(min_index != index) {
index_map[pq[index].second] = min_index;
index_map[pq[min_index].second] = index;
std::swap(pq[index], pq[min_index]);
sift_down(min_index);
}
}

// Extract the minimum element from priority queue.
std::pair <int, int> extract_min() {
index_map[pq[0].second] = size-1;
index_map[pq[size-1].second] = 0;
std::swap(pq[0], pq[size-1]);
size -= 1;
sift_down(0);
return pq[size];
}

// Change the value at index 'index' to 'value'.
void decrease_key(int index, int value) {
int temp = pq[index].first;
pq[index].first = value;
if(value < temp)
sift_up(index);
else
sift_down(index);
}

// Initialise and heapify the priority queue.
void make_heap(int start_index) {
for(int i = 0; i < SIZE; i++) {
pq[i].first = INF;
pq[i].second = i;
}
pq[0].first = 0;
pq[start_index].second = start_index;

for(int i = SIZE-1; i >= 0; i--)
sift_down(i);
}

int main() {

/* Graph is represent using adjacency list. It takes the following form:
graph[u] = {{v_1, c_1}, {v_2, c_2}, ..., {v_n, c_n}};
The above line means that there is an undirected edge
between vertices 'u' and 'v_1' with cost 'c_1'.
Similarly for (u, v_2, c_2), ..., (u, v_n, c_n).
*/
std::vector <std::vector <std::pair <int, int> > > graph (SIZE);

graph[0] = {{1, 20}, {2, 50}, {3, 70}, {4, 90}};
graph[1] = {{0, 20}, {2, 30}};
graph[2] = {{0, 50}, {1, 30}, {3, 40}};
graph[3] = {{0, 70}, {2, 40}, {4, 60}};
graph[4] = {{0, 90}, {3, 60}};

int visited[SIZE];
memset(visited, 0, sizeof(visited));
visited[0] = 1;
make_heap(0);           // Assuming algorithm to start from vertex 0.

for(int i = 0; i < SIZE; i++)
index_map[pq[i].second] = i;

int answer = 0;
while(size != 0) {

std::pair <int, int> p = extract_min();
/* p.first will contain the cost of the next edge to be added in our
answer and p.second will give the vertex number.
*/
visited[p.second] = 1;
answer += p.first;

for(int i = 0; i < graph[p.second].size(); i++) {
if(!visited[graph[p.second][i].first]) {
if(graph[p.second][i].second < pq[index_map[graph[p.second][i].first]].first) {
decrease_key(index_map[graph[p.second][i].first], graph[p.second][i].second);
}
}
}

}
std::cout << answer << "\n";
}

Я нашел способ реализовать алгоритм с помощью

std::priority_queue

Изменяя подход, хотел бы поделиться своим кодом

    #include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<limits.h>
#include<map>
#include<stack>
#include<stdio.h>
#include<queue>
#include<cmath>
#include<string.h>

using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define PII pair<int,int>
vector<PII> v[3001];
bool vis[3001];
int sum=0;
void prim(int s)
{
int y,x,i;
PII p;
priority_queue<PII, vector<PII> , greater<PII> > q;
q.push(mp(0,s));
while(!q.empty())
{
p = q.top();
q.pop();
x = p.ss;
if(vis[x]==true)
continue;
sum+=p.ff;
vis[x]=true;
for(i=0;i<v[x].size();i++)
{
y = v[x][i].ss;
if(vis[y]==false)
q.push(v[x][i]);
}
}
}
int main() {

fast
int f1=0,max=0,y,a1,x,j,w=0,f=0,l,m,b,c1=0,r=0;
char t,a[4][4],c;
int n,i=0,d=1,k;
cin>>n>>k;
for(x=0;x<k;x++)
{
cin>>i>>j>>r;
v[i].pb(mp(r,j));
v[j].pb(mp(r,i));
}
cin>>i;
prim(i);
cout<<sum;
return 0;

}