zoj 1586 QS Network

时间：2023-03-08 16:24:10

最小生成树，刚刚学了Prim算法。

对每条边变的权值进行预处理，c[i][j] = c[i][j] + p[i] + p[j] 其中c[i][j]为输入的权值，p[i]，p[j]为连接这两个节点所需的费用。

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

using namespace std;

const int maxn = ;

int c[maxn][maxn];//邻接矩阵

int x[maxn], y[maxn]; //x数组表示i节点到集合的最短距离 y数组表示i节点和集合中哪个点是最短距离

int p[maxn];

int main()

{

    int sb;

    scanf("%d", &sb);

    while (sb--)

    {

        int n, m, i, j, u, v, cost;

        scanf("%d", &n);

        for (i = ; i <= n; i++) scanf("%d", &p[i]);

        for (i = ; i <= n; i++) for (j = ; j <= n; j++) scanf("%d", &c[i][j]);

        for (i = ; i <= n; i++) for (j = ; j <= n; j++) c[i][j] = c[i][j] + p[i] + p[j];

        for (i = ; i <= n; i++) x[i] = c[][i], y[i] = ;

        y[] = -;// y[i] == -1 表示i节点已经放入了集合

        int tot = ;//已经有一个点放入了集合

        int ans = ;

        while ()

        {

            int mincost = 0x7FFFFFFF, v, flag = ;

            for (i = ; i <= n; i++) if (y[i] != - && x[i] < mincost) flag = , v = i, mincost = x[i];

            if (!flag) break;

            y[v] = -; tot++; ans = ans + x[v];

            for (i = ; i <= n; i++) if (y[i] != - && c[v][i] < x[i]) x[i] = c[v][i], y[i] = v;

        }

        if (tot == n)printf("%d\n", ans);

        else printf("No Way!\n");

    }

    return ;

}

相关文章