补时间

测试数据 #0: Accepted, time = 0 ms, mem = 2460 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 2464 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 2460 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 2464 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 2464 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 2460 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 2460 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 2460 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 2460 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 2464 KiB, score = 10

我的代码更快，只有三个15ms

#include <stdio.h>
#include <algorithm>

#define size 100001
#define j (i + 1)

typedef struct node {
    int val, to, from;
    const bool operator<(const node& o) const {
      return val < o.val;
  }
} node;

node a[size];
int uset[size], depth[size], n;

int find(int x) {
    return x == uset[x] ? x : (find(uset[x]));
//  return x == uset[x] ? x : (uset[x] = find(uset[x]));
}

int main(int argc, const char *argv[]) {
    int i, m, x, y, z, w;
    scanf("%i %i", &n, &m);
    for (i = 1; i <= n; ++i) {
        uset[i] = i;
    }
    m <<= 1;
    for (i = 0; i < m; i += 2) {
        scanf("%i %i %i", &a[i].from, &a[i].to, &a[i].val);
        a[j].val = a[i].val;
        a[j].from = a[i].to;
        a[j].to = a[i].from;
    }
    std::sort(a, a + m);
    x = 0;
    y = -1;
    for (i = 0; i < m; ++i) {
        w = find(a[i].from);
    z = find(a[i].to);
        if (w != z) {
            uset[w] = z;
            if (a[i].val > y) {
                y = a[i].val;
            }
            ++x;
        }
    }
    printf("%i %i", x, y);
    return 0;
}

/*
4 5
1 2 3
1 4 5
2 4 7
2 3 6
3 4 8
*/

读入优化

ios::sync_with_stdio(false);

cin读入是很慢的，用scanf吧，或者把什么同步关掉，百度一下好了

这里好像保存数据上没有用链表的必要。。。
有些傻了。。。
删去链表之后的代码贴上：

#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
const int maxm=90000,maxn=300;
int u[maxm],v[maxm],w[maxm],ans,r[maxm],p[maxm],n,m,s;
bool choose[maxm];
int find(int k){return((p[k]==k)?k:find(p[k]));}
int cmp(const int i,const int j){return w[i]<w[j];}
void kruskal()
{
s=0;ans=-1;
for (int i=1;i<=n;i++)p[i]=i;
for (int i=0;i<2*m;i++)r[i]=i;
sort(r,r+m*2,cmp);
for (int i=0;i<m*2;i++)
{
int e=r[i],x=find(u[e]),y=find(v[e]);
if (x!=y)
{
p[x]=y;
if (w[e]>ans)ans=w[e];
s++;
}
}
}
int main()
{
cin>>n>>m;
for (int i=0;i<m*2;i+=2)
{
cin>>u[i]>>v[i]>>w[i];
u[i+1]=v[i];v[i+1]=u[i];w[i+1]=w[i];
}
kruskal();
cout<<s<<" "<<ans;
}
不过按照常理说，这样应该更快吧，事实竟然很残酷。。。
测试数据 #0: Accepted, time = 105 ms, mem = 2080 KiB, score = 10
测试数据 #1: Accepted, time = 31 ms, mem = 2080 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 2080 KiB, score = 10
测试数据 #3: Accepted, time = 31 ms, mem = 2080 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 2080 KiB, score = 10
测试数据 #5: Accepted, time = 30 ms, mem = 2080 KiB, score = 10
测试数据 #6: Accepted, time = 44 ms, mem = 2080 KiB, score = 10
测试数据 #7: Accepted, time = 43 ms, mem = 2080 KiB, score = 10
测试数据 #8: Accepted, time = 46 ms, mem = 2080 KiB, score = 10
测试数据 #9: Accepted, time = 74 ms, mem = 2080 KiB, score = 10
Summary: Accepted, time = 434 ms, mem = 2080 KiB, score = 100
为什么时间更长了呢？

构思了一下觉得可以用桶排，利用哈希解决冲突的方法解决冲突问题，注意把数组开大一点，这样或许会更快

为什么要用链表？
刚打了一个也没到0ms，话说楼下说用spfa，恕我愚钝我怎么都想不到用spfa请指教
测试数据 #0: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

测试数据 #1: Accepted, time = 0 ms, mem = 1256 KiB, score = 10

测试数据 #2: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

测试数据 #3: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

测试数据 #4: Accepted, time = 0 ms, mem = 1256 KiB, score = 10

测试数据 #5: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

测试数据 #6: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

测试数据 #7: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

测试数据 #8: Accepted, time = 0 ms, mem = 1256 KiB, score = 10

测试数据 #9: Accepted, time = 15 ms, mem = 1256 KiB, score = 10

Summary: Accepted, time = 105 ms, mem = 1256 KiB, score = 100

#include <cstdio>
#include <algorithm>
using namespace std;
struct xxx{
int x,y,val;
}a[90001];
int n,m,f[301],l,MX;
int getfather(int v){
if(f[v]==v)return v;
else return f[v]=getfather(f[v]);
}
bool cmp(const xxx &a,const xxx &b){return a.val<b.val;}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=m;++i)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].val);
sort(a+1,a+1+m,cmp);
for (int i=1;i<=n;++i)f[i]=i;
for (int i=1;i<=m;++i)
if(getfather(a[i].x)!=getfather(a[i].y)){
f[f[a[i].y]]=f[a[i].x];
++l;
MX=max(a[i].val,MX);
}
printf("%d %d\n",l,MX);
}

@vistaswx 哪台是超算？

你需要spfa