如何减少 priority_queue<PI, vector<PI> 中特定边缘的密钥，更大的<PI> >，试图实现 prim 的算法？
How to decrease key for a particular edge in a priority_queue<PI, vector<PI> ,greater<PI> >,trying to implement prim's algorithm?
#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;
}
I was not able to implement the function which searches a particular
value i.e the vertex and changes it's key value instead I pushed the
changed pair, using
pp.push(mp(b,a));
I was able to get some test cases right by using the if statement
if(c==n)
break;
where 'c' represents the count of vertexes visited.
C++中的priority_queue没有提供减键操作的功能，这意味着我们无法在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 不允许在其内部达到峰值，因此无法更改优先级键。这是一个经典的队列实现，在一侧推送元素并在另一侧弹出它们。因此，您可能应该寻找堆数据结构的更通用的实现。
如果您坚持使用 std::priority_queue，您可能需要做一些丑陋的事情，例如将完整的队列内容弹出到向量、更新元素和恢复队列。
我知道三种方法。
如果你坚持使用标准库的priority_queue，你可以多次插入每个顶点，但每次看到它时都忽略它，除了第一个。在您的代码中，您可以将 if(vis[i]!=1) w=w+pp.top().ff; 更改为 if(vis[i]==1) continue; （也许；未测试）。缺点是您的 priority_queue 可以增长到 O(|E|) 内存。
您也可以使用标准库的 set 而不是 priority_queue。然后，每当你想插入一对 (distance, vertex) 时，首先你必须找到并删除 (old_distance, vertex) 对（如果它在集合中）。要始终了解每个 vertex 的 old_distance，您必须维护一个包含当前距离的数组（或向量）。这样，您将内存保持为 O(|V|)，但 set 的常数因子大于 priority_queue.
最后，你可以实现一个允许删除的优先级队列。假设您将优先级队列实现为二叉堆。然后，您将必须维护优先级队列中元素的逆排列：对于每个元素 v，存储和跟踪 v 的当前堆索引是什么。其中一个 看起来像是实现了这种方法，逆排列是 index_map.
我找到了一种使用
实现算法的方法
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;
}
#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;
}
I was not able to implement the function which searches a particular value i.e the vertex and changes it's key value instead I pushed the changed pair, using
pp.push(mp(b,a));
I was able to get some test cases right by using the if statement
if(c==n)
break;
where 'c' represents the count of vertexes visited.
priority_queue没有提供减键操作的功能，这意味着我们无法在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 不允许在其内部达到峰值，因此无法更改优先级键。这是一个经典的队列实现，在一侧推送元素并在另一侧弹出它们。因此，您可能应该寻找堆数据结构的更通用的实现。
如果您坚持使用 std::priority_queue，您可能需要做一些丑陋的事情，例如将完整的队列内容弹出到向量、更新元素和恢复队列。
我知道三种方法。
如果你坚持使用标准库的
priority_queue，你可以多次插入每个顶点，但每次看到它时都忽略它，除了第一个。在您的代码中，您可以将if(vis[i]!=1) w=w+pp.top().ff;更改为if(vis[i]==1) continue;（也许；未测试）。缺点是您的priority_queue可以增长到 O(|E|) 内存。您也可以使用标准库的
set而不是priority_queue。然后，每当你想插入一对(distance, vertex)时，首先你必须找到并删除(old_distance, vertex)对（如果它在集合中）。要始终了解每个vertex的old_distance，您必须维护一个包含当前距离的数组（或向量）。这样，您将内存保持为 O(|V|)，但set的常数因子大于priority_queue.最后，你可以实现一个允许删除的优先级队列。假设您将优先级队列实现为二叉堆。然后，您将必须维护优先级队列中元素的逆排列：对于每个元素
v，存储和跟踪v的当前堆索引是什么。其中一个index_map.
我找到了一种使用
实现算法的方法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;
}