题目描述
例如，给出一个无向图，找出最小生成树。如果图不连接，则输出orz。
输入格式
第一行包含两个整数N,MN,M，表示图共有NN个结点和MM条无向边。
接下来MM每行包含三个整数X_i,Y_i,Z_iXi,Yi,Zi，这意味着有一个长度Z_iZi无向边连接点X_i,Y_iXi,Yi。
输出格式
如果图片连接，则输出一个整数表示生成树的最小长度之和。如果图片不连接，则输出orz。
输入输出样例
复制
4 5 1 2 2 1 3 2 1 4 3 2 3 4 3 4 3
复制
7
说明/提示
数据规模：
对于20\ %的数据，N\le 5N≤5，M\le 20M≤20。
对于40\@%的数据，N\le 50N≤50，M\le 2500M≤2500。
对于70\p%的数据，N\le 500N≤500，M\le 10^4M≤104。
对于100\0%的数据：1\le N\le 50001≤N≤5000，1\le M\le 2\times 10^51≤M≤2×105，1\le Z_i \le 10^41≤Zi≤104。
#include<iostream> #include<cstring> #define MAXVEX 5001 #define INFINITY 99999 using namespace std; int arc[MAXVEX][MAXVEX]; int visited[MAXVEX]; int lowcost[MAXVEX]; int main(){ int ans = 0; int m,n,k,min; cin>>n>>m; for(int i=0; i<=n; i ) for(int j=0; j<=n; j ){ if( i != j) arc[i][j] = INFINITY; } for(int i=1; i<=m; i ){ int x, y, z; cin>>x>>y>>z; if(z < arc[x][y]) arc[x][y] = arc[y][x] = z; } for(int i=1; i<=n; i ) lowcost[i] = arc[1][i]; lowcost[1] = 0; visited[1] = 1; for(int i=2; i<=n; i ){ k = 0; min = INFINITY; for(int j=2; j<=n; j ){ if(!visited[j] && (lowcost[j] < min)){ min = lowcost[j]; k = j; } } visited[k] = 1; ans = lowcost[k]; if(k == 0) { cout<<"orz"<<endl; return 0; } for(int j=1; j<=n; j ){ if(!visited[j] && (arc[k][j] < lowcost[j])){ lowcost[j] = arc[k][j]; } } } cout<<ans<<endl; return 0; }