Как уменьшить ключ для конкретного ребра в приоритете_queue <PI, vector <PI>, больше <PI>>, пытаясь реализовать алгоритм примитива?

Question

#include <bits/stdc++.h> 
using namespace std; 

#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 
#define LL long long int 
#define pb push_back 
#define mp make_pair 
#define PI pair<int,int> 
#define PL pair<LL,LL> 
#define PIS pair< int,string> 


#define test int t;cin>>t;while(t--) 
#define ff first 
#define ss second 
#define INF 1000000000 
#define input(a,n) for(i=1;i<=n;i++)cin>>a[i]; 
#define output(a,n) for(i=1;i<=n;i++)cout<<a[i]<<" "; 
vector< vector<LL> >v(3002, vector<LL>(3002,-1)); 
priority_queue<PI, vector<PI> ,greater<PI> > pp; 
LL w=0; 
int vis[3002]={0}; 
/*void deck(int a ,int b, int *k) 
{ 
    while(!pp.empty()) 
    { 
     i=pp.top.ss; 
     if(i==a) 
      pp.top 
    } 
}*/ 
void prim(LL s, LL *k, LL *p,LL n) 
{ 

    pp.push(mp(0,s)); 
    k[s]=0; 
    LL i,x,a,b,c=0; 
    vector<PI >::iterator it; 
    while(true) 
    { 
     if(c==n) 
      break; 
     i=pp.top().ss; 
     //cout<<i<<" "; 
     if(vis[i]!=1) 
     w=w+pp.top().ff; 
     vis[i]=1; 
     c++; 
     pp.pop(); 
     for(x=1;x<=n;x++) 
     { 
      if(v[i][x]!=-1) 
      { 

      a=x; 
      b=v[i][x]; 
      if(!vis[a] && b<k[a]) 
      { 
       k[a]=b; 
       p[a]=i; 
       pp.push(mp(b,a)); 

      } 
      } 
     } 
    } 
} 
int main() 
{ 
    fast 

    LL n,m,x,i,j,r,s; 
    /*pp.push(mp(2,3)); 
    pp.push(mp(3,4));*/ 
    cin>>n>>m; 
    LL k[n+1],p[n+1]; 
    v.resize(n+1); 
    for(x=1;x<n+1;x++) 
    { 
     k[x]=INF; 
     p[x]=-1; 
    } 
    for(x=0;x<m;x++) 
    { 
     cin>>i>>j>>r; 
     /*v[i].pb(mp(j,r)); 
     v[j].pb(mp(i,r));*/ 
     if(v[i][j]!=-1) 
     { 
      if(v[i][j]>r) 
      { 
       v[i][j]=r; 
       v[j][i]=r; 
      } 
     } 
     else 
     { 
      v[i][j]=r; 
      v[j][i]=r; 
     } 


    } 
    cin>>s; 
    prim(s,k,p,n); 
    cout<<w; 
    //cout<<pp.top().ss;  
} 

я не смог реализовать функцию, которая ищет конкретный значение т.е. вершины и изменяет это значение ключа вместо этого я нажал на измененную пару , используя

pp.push(mp(b,a)); 

I был в состоянии получить некоторые тестовые примеры с использованием заявления if

if(c==n) 
break; 

где 'c' представляет собой количество посещенных вершин.

Answer 1

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

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; 

} 

Answer 2

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"; 
} 

Answer 3

Стандартная std::priority_queue не позволяет достигнуть максимума внутри так изменения приоритета ключей не представляется возможным. Это классическая реализация очереди с нажатием элементов на одной стороне и повторение их на другом. Поэтому, вероятно, вам следует искать более общую реализацию структуры данных кучи.

Если вы настаиваете на использовании std::priority_queue, вам может потребоваться сделать что-то столь же уродливое, как вывести полный контент очереди в вектор, обновить элементы и восстановить очередь.

Answer 4

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

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. Один из other answers выглядит так, как будто он реализует этот подход, а обратная перестановка - index_map.