帮助我的奖励10000000000000000000000000%10个金币啊
by 魏之哲它椰叶 @ 2019-03-01 20:24:50
或许你可以先学完整的克鲁斯卡尔再写这个题
by Lance1ot @ 2019-03-01 20:34:02
@[Lance1ot](/space/show?uid=28007) 可是套并查集模板……为什么不可以……
by 魏之哲它椰叶 @ 2019-03-01 20:36:28
@[魏之哲它椰叶](/space/show?uid=171518) 冰茶姬很快的呀。。。怎么会$T$
把我的代码贴上吧
```
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#define For(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
const int INF=0x1fffffff;
struct qwq
{
int x,y,t;
}a[100001];
int n,m,bin[1001],ans,s;
int anc(int k)
{
if(!bin[k])
return k;
return bin[k]=anc(bin[k]);
}
bool link(int a,int b,int k)
{
a=anc(a);
b=anc(b);
if(a!=b)
{
++ans;
bin[a]=b;
return 1;
}
return 0;
}
bool cmp(qwq a,qwq b)
{
return a.t<b.t;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
For(i,1,m)
cin>>a[i].x>>a[i].y>>a[i].t;
sort(a+1,a+m+1,cmp);
for(int i=1;i<=m;++i)
if(link(a[i].x,a[i].y,i))
s=max(s,a[i].t);
if(ans<n-1)
cout<<-1<<endl;
else
cout<<s<<endl;
return 0;
}
```
by 绝顶我为峰 @ 2019-03-01 20:41:46
@[魏之哲它椰叶](/space/show?uid=171518)
```cpp
for(int i=1;i<=m;i++)
{
pd=1;
a[bcj(s[i].z)]=bcj(s[i].x);
for(int j=1;j<m;j++)
if(bcj(s[j].z)!=bcj(s[j+1].x))pd=0;
if(pd==1)
{
cout<<s[i].y;
return 0;
}
}
```
这段代码时间复杂度是$O(m^2)$的啊
极端情况下很容易被卡的
by Lance1ot @ 2019-03-01 20:43:22
这么写是可以的
```cpp
int ans=0;
for(int i=1;i<=m;i++)
{
int fa=bcj(s[i].z),fb=bcj(s[i].x);
if(fa==fb) continue;
a[fa]=fb;
ans=max(s[i].y);
}
cout<<ans;
```
by Lance1ot @ 2019-03-01 20:46:16
@[Lance1ot](/space/show?uid=28007) 你代码里的 ``` ans=max(s[i].y);```
错了吧
by 魏之哲它椰叶 @ 2019-03-01 20:57:53
@[魏之哲它椰叶](/space/show?uid=171518)
大概就是那个意思了
qwq
毕竟不是我的code qwq
by Lance1ot @ 2019-03-01 21:28:37
@[蒟蒻烟雨平生](/space/show?uid=85682) 现在我的思路与你基本相似了，可是反而连样例都错了？？？
```
#include<bits/stdc++.h>
using namespace std;
int n,m,z,x,y,a[1010],lu=0,ss;
struct QAQ
{
int z,x,y;
}s[100002];
int bcj(int x)
{
if(a[x]==x)return x;
return a[x]=bcj(a[x]);
}
bool cr(int aa,int bb){
int ba=bcj(aa);
int fa=bcj(bb);
if(ba!=fa)
{
a[fa]=ba;
lu++;
return 1;
}
return 0;
}
bool tmd(QAQ d, QAQ e)
{
return d.y<e.y;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)a[i]=i;
for(int i=1;i<=m;i++)
{
cin>>s[i].z>>s[i].x>>s[i].y;
if(s[i].z>s[i].x)swap(s[i].z,s[i].x);
}
sort(s+1,s+m+1,tmd);
for(int i=1;i<=m;i++)
{
if(cr(s[i].z,s[i].x));
ss=max(ss,s[i].y);
}
if(lu<n-1)cout<<-1;
else cout<<ss;
}
```
by 魏之哲它椰叶 @ 2019-03-01 21:33:21
@[魏之哲它椰叶](/space/show?uid=171518) 把
```
swap(s[i].z,s[i].x);
```
删掉
by 绝顶我为峰 @ 2019-03-01 21:48:36