算法分析
时间复杂度 $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);
}
}
大佬,问一下Java为什么要这样读入呢?
String[] str1 = reader.readLine().split(” “);
n = Integer.parseInt(str1[0]);
m = Integer.parseInt(str1[1]);
比Scanner要快
嗯,知道了,谢谢大佬