Hust oj 2038 联系网络(MST）

TwIStOy要建立一个联系网络，这样可以方便的联系到所有人。如果TwIStOy可以联系到A，A又可以联系到B，那么就认为

TwIStOy可以联系到B了。但是建立两个人之间的联系方式是需要一定的代价的，现在TwIStOy希望使用一个最小的代价联系到

所有人。

本题有多组数据，输入处理到文件结束。

每组输入第一行包括一个整数n，表示有n个人编号分别是0 ～ (n-1)。TwIStOy的编号总是0。

接下来的n行每行包括n个整数，第i行的第j个整数w表示编号为i的联系到编号为j的人所需要的代价是w。

当然这个是一定满足w[i,j] = w[j,i]的。

n <= 300

3

0 2 3

2 0 1

3 1 0

3

TwIStOy

水题，看完题就知道是求最小生成树，直接裸Prim模板AC

#include<iostream>
#include<cstdio>
using namespace std;int cost[305][305];
int mincost[305];
bool used[305];
const int Inf = 0X3f3f3f;
int V;int prim()
{for(int i = 0; i < V; i++){mincost[i] = Inf;used[i] = false;}mincost[0] = 0;int res = 0;while (true ) {int v = -1;for(int u = 0; u < V; u++){if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u;}if (v == -1) break;used[v] = true;res += mincost[v];for(int u = 0; u < V; u++){mincost[u] = min(mincost[u],cost[v][u]);}}return res;
}int main()
{while(~scanf("%d",&V)){int i,j,k;int x,y,z;for(i=0;i<V;i++){for(j=0;j<V;j++){scanf("%d",&cost[i][j]);}}cout<<prim()<<endl;}}