学步园

 

 

标题：	近似算法求解旅行售货员问题
时 限：	1000 ms
内存限制：	10000 K
总时限：	3000 ms
描述：	有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。假定所有输入的根节点或者源为第一个城市或第一组数据。
输入：	n（城市数，1<=n<=100）； e（边数）； 以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。
输出：	n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。
输入样例：	5 8 1 2 2 1 3 12 1 4 10 2 3 8 2 5 9 3 4 6 3 5 3 4 5 7
输出样例：	30

import java.util.Scanner;

public class Main {
    static int n = 0;
    static float[][] c = null;
    static int mincost = 0;

    public static void prim(int n, float[][] c) {
        float[] lowcost = new float[n + 1];
        int[] closest = new int[n + 1];
        boolean[] s = new boolean[n + 1];

        s[1] = true;

        for (int i = 2; i <= n; i++) {
            lowcost[i] = c[1][i];
            closest[i] = 1;
            s[i] = false;
        }

        int m = 1;
        for (int i = 1; i < n; i++) {
            float temp = Float.MAX_VALUE;
            int j = 1;
            for (int j2 = 2; j2 <= n; j2++) {
                if ((!s[j2]) && (lowcost[j2] < temp)) {
                    temp = lowcost[j2];
                    j = j2;
                }
            }

            // System.out.println(closest[j]+ " "+j );
            mincost = mincost + (int) c[m][j];
            m = j;

            if (i == n - 1) {
                mincost = mincost + (int) c[j][1];
            }
            s[j] = true;

            for (int k = 2; k <= n; k++) {
                if ((c[j][k] < lowcost[k]) && (!s[k])) {
                    lowcost[k] = c[j][k];
                    closest[k] = j;
                }
            }
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner myscanner = new Scanner(System.in);
        n = myscanner.nextInt();
        int e = 0;
        e = myscanner.nextInt();
        c = new float[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                c[i][j] = Float.MAX_VALUE;
            }
        }
        for (int i = 0; i < e; i++) {
            int ix = myscanner.nextInt();
            int iy = myscanner.nextInt();
            int wij = myscanner.nextInt();
            //无向边
            c[ix][iy] = wij;
            c[iy][ix] = wij;
        }

        Main.prim(n, c);

        System.out.println(mincost);
    }
}