Poj 2395 Out of Hay( 最小生成树 )

题意：求最小生成树中最大的一条边。

分析：求最小生成树，可用Prim和Kruskal算法。一般稀疏图用Kruskal比较适合，稠密图用Prim。由于Kruskal的思想是把非连通的N个顶点用最小的代价构成一个连通分量，这与并查集的思想类似，所以可以用并查集来实现Kruskal。

import java.util.Scanner;

/**

 * 稀疏图用Prim,21316K，3047MS 不划算、

 */

public class Poj_2395_Prim {

	static int n,m;

	static int[][] map=new int[2010][2010];

	static boolean vis[]=new boolean[2010];

	public static int prime() {

		int i,j,min,flag = 0,max=-1;

		vis[1]=true;

		for(i=2;i<=n;i++){

			min=Integer.MAX_VALUE;

			flag=0;

			for(j=1;j<=n;j++){

				if(!vis[j] && map[1][j] < min){

					min=map[1][j];

					flag=j;

				}

			}

			vis[flag]=true;

			max = max < min ? min : max;

			for(j=1;j<=n;j++){

				if(!vis[j] && map[flag][j] <map[1][j]){

					map[1][j]=map[flag][j];

				}

			}

		}

		return max;

	}

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();

		m = sc.nextInt();

		for(int i=1;i<=n;i++){

			for(int j=1;j<=n;j++){

				map[i][j]=Integer.MAX_VALUE;

			}

			map[i][i]=0;

		}

		for (int i = 1; i <= m; i++) {

			int s=sc.nextInt();

			int e=sc.nextInt();

			int val=sc.nextInt();

			if(map[s][e] > val){

				map[s][e] = val;

				map[e][s]=val;

			}

		}

		System.out.println(prime());

	}

}

import java.util.ArrayList;

import java.util.Collections;

import java.util.Comparator;

import java.util.Scanner;

class Edge{

	int s;

	int e;

	int val;

	public Edge(int s,int e,int val){

		this.s=s;

		this.e=e;

		this.val=val;

	}

}

class Com implements Comparator<Edge>{

	@Override

	public int compare(Edge o1, Edge o2) {

		// TODO Auto-generated method stub

		return o1.val - o2.val;

	}

}

/**

*Kruskal

 */

public class Poj_2395_kruskal {

	static int n,m;

	static int MAX = 4000000;

	static ArrayList<Edge> list = new ArrayList<Edge>();

	static int set[] = new int[MAX];

	static void init_set(){

		for(int i=1;i<=n;i++){

			set[i]=i;

		}

	}

	static int find(int a){

		if(set[a] == a){

			return a;

		}else{

			return set[a]=find(set[a]);

		}

	}

	static void unite(int x,int y){

		x = find(x);

		y = find(y);

		if (x == y)

			return;

		if (y < x)

			set[x] = y;

		else if (y > x)

			set[y] = x;

	}

	static boolean same(int x, int y){

		return find(x) == find(y);

	}

	static int kruskal(){

		int ans=-1;

		init_set();

		for(int i=0;i < list.size();i++){

			Edge e =list.get(i);

			if (!same(e.s, e.e)){

				unite(e.s, e.e);

				if (ans < e.val)

					ans = e.val;

			}

		}

		return ans;

	}

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();

		m = sc.nextInt();

		for (int i = 1; i <= m; i++) {

			int s=sc.nextInt();

			int e=sc.nextInt();

			int val=sc.nextInt();

			list.add(new Edge(s,e,val));

		}

		Collections.sort(list,new Com());

		System.out.println(kruskal());

	}

}

巴特西

Poj 2395 Out of Hay( 最小生成树 )

最新文章

热门文章