Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
313ms 还很稚嫩import java.io.*; import java.util.*; public class Main{ public static final int N=110; public static final int INF=(1<<30); public static boolean []vis=new boolean[N]; public static int [][]edge=new int[N][N]; public static int []low=new int [N]; public static int sum; static int min(int a,int b){ return a<b?a:b; } static void prim(int n){ sum=0; Arrays.fill(vis,false); vis[1]=true; for(int i=1;i<=n;i++){ low[i]=edge[1][i]; } for(int i=1;i<n;i++){ int Minlow=INF,idx=-1; for(int j=1;j<=n;j++){ if(!vis[j]&&low[j]<Minlow){ Minlow=low[j]; idx=j; } } vis[idx]=true; sum+=Minlow; for(int j=1;j<=n;j++){ if(!vis[j]){ low[j]=min(low[j],edge[idx][j]); } } } } public static void main(String []args){ Scanner cin=new Scanner(System.in); while(cin.hasNext()){ int n=cin.nextInt(); for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ edge[i][j]=cin.nextInt(); } } prim(n); System.out.println(sum); } } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator