如何在priority_queue< PI>向量< 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?
本文介绍了如何在priority_queue< PI>向量< PI>中减小针对特定边缘的密钥. ,更大的PI. > ;,尝试实施prim的算法?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
#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));
我可以通过使用if语句来获得一些测试用例
I was able to get some test cases right by using the if statement
if(c==n)
break;
其中"c"代表访问的顶点数.
where 'c' represents the count of vertexes visited.
推荐答案
我找到了一种使用以下方法实现算法的方法
I found a way to implement the algorithm using
std::priority_queue
通过更改方法,希望共享我的代码
By changing approach, would like to share my code
#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;
}
这篇关于如何在priority_queue< PI>向量< PI>中减小针对特定边缘的密钥. ,更大的PI. > ;,尝试实施prim的算法?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文