看discuss发现样例有问题
#include<cstdio> #include<algorithm> #define INF 0x3f3f3f3f using namespace std; struct Edge { int l,r; int val; } edge[15055],res[1055]; bool cmp(const Edge x,const Edge y) { return x.val<y.val; } int V,E; int tree[1005]; int find(int x) { return tree[x]==x?x:tree[x]=find(tree[x]); } void Kruskal() { int ans = 0,cnt = 0,Max = 0; for(int i = 1; i<=V; ++i) tree[i] = i; for(int i = 0; i<E; ++i) { int x = find(edge[i].l); int y = find(edge[i].r); if(x!=y) { tree[x] = y; res[cnt].l = edge[i].l; res[cnt].r = edge[i].r; res[cnt++].val = edge[i].val; } if(cnt==V-1) break; } printf("%d\n",res[cnt-1].val); printf("%d\n",cnt); for(int i = 0; i<cnt; ++i) printf("%d %d\n",res[i].l,res[i].r); } int main() { while(~scanf("%d%d",&V,&E)) { for(int i = 0; i<E; ++i) scanf("%d%d%d",&edge[i].l,&edge[i].r,&edge[i].val); sort(edge,edge+E,cmp); Kruskal(); } return 0; }