zoj 1586 QS Network
5457 ワード
最小生成ツリーは、Primアルゴリズムを習ったばかりです.
各エッジの重み値を前処理し、c[i][j]=c[i][j]+p[i]+p[j]のうちc[i][j]は入力された重み値であり、p[i],p[j]はこの2つのノードを接続するのに必要な費用である.
各エッジの重み値を前処理し、c[i][j]=c[i][j]+p[i]+p[j]のうちc[i][j]は入力された重み値であり、p[i],p[j]はこの2つのノードを接続するのに必要な費用である.
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
const int maxn = 1010;
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 = 1; i <= n; i++) scanf("%d", &p[i]);
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) scanf("%d", &c[i][j]);
for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) c[i][j] = c[i][j] + p[i] + p[j];
for (i = 1; i <= n; i++) x[i] = c[1][i], y[i] = 1;
y[1] = -1;// y[i] == -1 i
int tot = 1;//
int ans = 0;
while (1)
{
int mincost = 0x7FFFFFFF, v, flag = 0;
for (i = 1; i <= n; i++) if (y[i] != -1 && x[i] < mincost) flag = 1, v = i, mincost = x[i];
if (!flag) break;
y[v] = -1; tot++; ans = ans + x[v];
for (i = 1; i <= n; i++) if (y[i] != -1 && c[v][i] < x[i]) x[i] = c[v][i], y[i] = v;
}
if (tot == n)printf("%d
", ans);
else printf("No Way!
");
}
return 0;
}