POJ 1258

• 水题,prim板子

  #include <iostream>
  #include <string.h>
  #define INF 0x3f3f3f3f
  using namespace std;
  const int maxn = 1e3;
  
  int a[maxn][maxn];
  int vis[maxn];
  int dist[maxn];
  int n,m;
  
  void prim() {
      memset(vis, 0 ,sizeof vis);
      vis[1] = 1; //随便找一个点加入最小生成树中
      for (int i=1; i<=n; i++) dist[i] = a[1][i]; // 更新每个点到树的距离
  
      long long sum = 0;//最短的路径长度
      for (int i=1; i<n; i++) { // 开始找n-1条边
          long long minn = INF; // 距离树最短的边
          int point = INF; // 距离树最近的点
          for (int i=1; i<=n; i++) {
              if (!vis[i] && dist[i]<minn ) {
                  point = i;
                  minn = dist[i];
              }
          }
          vis[point] = true; // 该点访问过（在树中）
          sum += dist[point];
          for (int i=1; i<=n; i++) {
              if ( !vis[i] && a[point][i]<dist[i] )
                  dist[i] = a[point][i];
          }
      }
      printf("%d\n",sum);
  }
  int main() {
  //    freopen("a.txt","r",stdin);
  	while (scanf("%d",&n) != EOF) {
  	    memset(a,0x3f,sizeof a);
  	    for (int i=1; i<=n; i++) 
  	        for (int j=1; j<=n; j++) {
  	        	scanf("%d",&a[i][j]);
  //	        	if (i == j) a[i][j] = INF;
  	        }
  	    prim();
  	}
      return 0;
  }