Prim37分求助

lighthouse @ 2021-11-14 11:15:12

#include <bits/stdc++.h>

#define INF 10001

using namespace std;

int dis[5005];

int a[5005][5005];

bool vis[5005];

int main(){
    int n, m, mst = 0, tot = 0;
    cin >> n >> m;
    memset(a, 0x7f, sizeof(a));
    for(int i = 1;i <= n;i++){
        dis[i] = INF;
    }
    for(int i = 1;i <= m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = min(a[x][y], z);
        a[y][x] = min(a[y][x], z);
    }
    dis[1] = 0;
    for(int i = 1;i <= n;i++){
        int minn = INF, t = 1;
        for(int j = 1;j <= n;j++){
            if(vis[j] == 0 && dis[j] < minn){
                minn = dis[i];
                t = j;
            }
        }
        if(vis[t] == 1)
            continue;
        vis[t] = 1;
        for(int j = 1;j <= n;j++){
            if(vis[j] == 0 && a[t][j] < dis[j]){
                dis[j] = a[t][j];   
            }
        }
    }
    for(int i = 1;i <= n;i++){
        if(dis[i] == 10001) tot++;
        else mst += dis[i];
    }
    if(tot != 0) cout << "orz";
    else cout << mst;
    return 0;
}

by lighthouse @ 2021-11-14 11:15:46

其余点AC

by yangyuanxi44 @ 2021-11-14 11:24:24

借楼问一下，这道题我30分，不知道哪错了

code： https://www.luogu.com.cn/paste/pxht2n4v

by Mr_ll @ 2021-11-14 11:46:37

@yangyuanxi44 最小生成树一般用prim或克鲁斯卡尔求，您这，最后得到的不一定是一棵树吧

by Liweiang @ 2021-11-14 12:50:13

@Mr_ll 帮@yangyuanxi44 回复，他说他用的prim

by Mr_ll @ 2021-11-14 14:47:05

#include <bits/stdc++.h>

#define INF 10001

using namespace std;

int dis[5005];

int a[5005][5005];

bool vis[5005];

int main(){
    int n, m, mst = 0, tot = 0;
    cin >> n >> m;
    memset(a, 0x7f, sizeof(a));
    for(int i = 1;i <= n;i++){
        dis[i] = INF;
    }
    for(int i = 1;i <= m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        a[x][y] = min(a[x][y], z);
        a[y][x] = min(a[y][x], z);
    }
    dis[1] = 0;
    for(int i = 1;i <= n;i++){
        int minn = INF, t = 1;
        for(int j = 1;j <= n;j++){
            if(vis[j] == 0 && dis[j] < minn){
                minn = dis[i];//注意，就是这的，j敲成了i
                t = j;
            }
        }
        if(vis[t] == 1)
            continue;
        vis[t] = 1;
        for(int j = 1;j <= n;j++){
            if(vis[j] == 0 && a[t][j] < dis[j]){
                dis[j] = a[t][j];   
            }
        }
    }
    for(int i = 1;i <= n;i++){
        if(dis[i] == 10001) tot++;
        else mst += dis[i];
    }
    if(tot != 0) cout << "orz";
    else cout << mst;
    return 0;
}

by Mr_ll @ 2021-11-14 14:48:46

@lighthouse

by Mr_ll @ 2021-11-14 15:04:47

@yangyuanxi44 ,您那个排序挺高级的鸭，从大到小（雾），emm，vector我不太清楚，我觉得可能是先按编号排了点，其实应该是边权优先

代码我改了改，还没交（可能会TLE）

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> p;
int dis[1000005],head[1000005],n,m,cnt;
bool vis[1000005];
priority_queue<pair<int,int> >Q;
struct EDGE{
    int to,w,next;
}edge[1000005];
void init(){
    for(int i=0 ; i<=n ; i++)
        dis[i]=0x7fffffffffffffff;
}
void add(int u,int v,int w){
    cnt++;
    edge[cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
signed main(){
    cin>>n>>m;
    init();
    for(int i=1 ; i<=m ; i++){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    Q.push(make_pair(0,1));
    dis[1]=0;
    int e=0,ans=0; 
    while(!Q.empty()&&e<n){
        int root=Q.top().second,dis1=-Q.top().first;
        Q.pop();
        if(vis[root])
           continue;
        vis[root]=true;
        ans+=dis1;
        e++;
        for(int i=head[root] ; i!=0 ; i=edge[i].next){
            if(edge[i].w<dis[edge[i].to]){
                dis[edge[i].to]=edge[i].w;
                Q.push(make_pair(-dis[edge[i].to],edge[i].to));
            }   
        }
    }
    if(e==n)
       cout<<ans;
    else
       cout<<"orz";
    return 0;
}

by yangyuanxi44 @ 2021-11-14 15:26:42

@Mr_ll 谢谢大佬

by yangyuanxi44 @ 2021-11-14 15:32:15

@Mr_ll 谢谢大佬，过了，应该是优先队列小根堆弄错了，下次还是重载运算符吧,多谢多谢

by Mr_ll @ 2021-11-14 15:34:25

@yangyuanxi44 不用谢，正好又学了一下prim，（其实从未用过prim）