算法分析

时间复杂度 $O(n^2)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    static int n;
    static int m;
    static int q;
    static int N = 510;
    static int INF = 0x3f3f3f3f;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];//表示到集合的最短距离
    static boolean[] st = new boolean[N];
    public static int prim()
    {
        Arrays.fill(dist, INF);
        int res = 0;
        for(int i = 0;i < n;i++)
        {
            int t = -1;
            for(int j = 1;j <= n;j++)
            {
                if(!st[j] && (t == -1 || dist[t] > dist[j]))
                    t = j;
            }
            if(i != 0 && dist[t] == INF) return INF;
            //标记已加入集合
            st[t] = true;
            if(i != 0) res += dist[t];
            //用t更新其他点
            for(int j = 1;j <= n;j++) dist[j] = Math.min(dist[j], g[t][j]);
        }
        return res;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        for(int i = 1;i <= n;i++)
            for(int j = 1;j <= n;j++)
            {
                if(i == j) g[i][j] = 0;
                else g[i][j] = INF;
            }
        while(m -- > 0)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            g[a][b] = Math.min(g[a][b], c);
            g[b][a] = Math.min(g[b][a], c);
        }
        int t = prim();
        if(t == INF) System.out.println("impossible");
        else System.out.println(t);
    }
}