prim 求助,样例能过但wa

P3366 【模板】最小生成树

realyanhualengluo @ 2023-03-19 11:23:40

1)对于重边选择了最小的那一个


#include<iostream>
#include<algorithm>
using namespace std;
const int maxs = 50;
const int INF = 99999;
struct AMGraph {
    int vexs[maxs];//定点表
    int arr[maxs][maxs];//邻接矩阵
    int vexnum, arcnum;//顶点数,边数
};
void initGraph(AMGraph &G) {
    cin >> G.vexnum >> G.arcnum;
    for (int i = 1; i <= G.vexnum; i++) {
        G.vexs[i] = i;
    }
    for (int i = 1; i <= G.vexnum; i++) {
        for (int j = 1; j <= G.vexnum; j++) {
            G.arr[i][j] = INF;
        }
    }
}
void createGraph(AMGraph& G) {
    int i = 0, j = 0,w=0;
    for (int k = 1; k <= G.arcnum; k++) {
        cin >> i >> j>>w;
        if (w < G.arr[i][j]) {
            G.arr[i][j] = w;
        }
    }
}
void showGraph(AMGraph G)
{
    for (int i = 1; i <= G.vexnum; i++)
    {
        for (int j = 1; j <= G.vexnum; j++)
        {
            if (G.arr[i][j] == INF) //无穷大弄得更好看点
                cout << "∞" << " ";
            else
                cout << " " << G.arr[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
}
int d[maxs];//顶点与集合s的最短距离
int visit[maxs];//标志数组
int res = 0;//最小生成树的边权值
void prim(AMGraph& G) {
    //把数组初始化一下,除了1之外所有点到s集合的距离都是无穷
    fill(d + 1, d + G.vexnum + 1, INF);
    d[1] = 0;//一开始只有1和S集合距离为0
    visit[1] = 1;
    //用初始点的路径更新d数组
    for (int i = 2; i <= G.vexnum; i++) {
        d[i] = min(d[i], G.arr[1][i]);
    }
    for (int i = 2; i <= G.vexnum; i++) {
        int temp =INF;
        int t = -1;
        //找数组中距离s最小且没有加入集合s的点
        for (int j = 2; j <= G.vexnum; j++) {
            if (visit[j] == 0 && d[j] < temp) {
                temp = d[j];
                t = j;
            }
        }
        if (t == -1) {//找不到说明不是连通图
            res = INF;
            return;
        }
        visit[t] = 1;
        res += d[t];
        for (int j = 2; j <= G.vexnum; j++) {

            d[j] = min(d[j], G.arr[t][j]);
        }
    }
    if (res == INF) {
        cout << "orz";
    }
    else {
        cout << res;
    }

}
int main() {
    AMGraph G;
    initGraph(G);
    createGraph(G);
    showGraph(G);
    prim(G);
}

|