\(Graph\)

首先，看到最大值最小一定要二分，然后怎样判断呢？？

本来想在最短路上进行判断，自己把自己给\(Hash\)掉了，然后因为以前做过一道题目用的最小生成树，所以用最小生成树试了一下，发现可以过大样例。

具体证明也不会……

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
vector<ll>v;
const int N=8e3,M=2e5+100;
struct info{
    int s,e;
    ll v;
}id[M];
struct edge{
    int s,e;
    ll v;
    int net;
}ed[N<<1];
int n,m,k,tot;
int head[N],f[N],deep[N];
bool mark[N];
inline int getf(int x)
{
    return f[x]==x ? x:f[x]=getf(f[x]);
}
inline bool cmp(info a,info b)
{
    return a.v<b.v;
}
inline void add(int s,int e,ll v)
{
    ed[++tot]=(edge){s,e,v,head[s]};
    head[s]=tot;
    return ;
}
inline void work()
{
    for (int i=1;i<=n;i++) f[i]=i;
    int num=0;
    for (int i=1;i<=m;i++)
    {
        int a=getf(id[i].s),b=getf(id[i].e);
        if (a!=b)
        {
            f[a]=b;
            int s=id[i].s,e=id[i].e;
            ll v=id[i].v;
            add(s,e,v);add(e,s,v);
            num++;
            if (num==n-1) break;
        }
    }
    return ;
}
inline void up(int x)
{
    if (x==n) return ;
    for (int i=head[x];i;i=ed[i].net)
    if (deep[ed[i].e]<deep[x])
    {
        v.push_back(ed[i].v);
        up(ed[i].e);
    }
    return ;
}
inline bool check(ll mid)
{
    ll now=0,num=0;
    for (int i=0;i<(int)v.size();i++)
    {
        if (v[i]>mid) return 0;
        if (now+v[i]>mid)
        {
            now=0;
            num++;
            if (num>k) return 0;
        }
        now+=v[i];
    }
    return 1;
}
inline void dfs(int x,int fa)
{
    deep[x]=deep[fa]+1;
    for (int i=head[x];i;i=ed[i].net)
    if (ed[i].e!=fa)
    dfs(ed[i].e,x);
    return ;
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if (m==0)
    {
        printf("-1\n");
        return 0;
    }
    ll sum=0;
    for (int i=1;i<=m;i++)
    {
        int s,e;
        ll v;
        scanf("%d%d%lld",&s,&e,&v);
        id[i]=(info){s,e,v};
        sum+=v;
    }
    sort(id+1,id+m+1,cmp);
    work();
    dfs(n,0);
    up(1);
    ll l=0,r=sum,mid=(l+r)>>1,ans;
    while (l<=r)
    {
        if (check(mid))
        {
            r=mid-1;
            ans=mid;
        }
        else l=mid+1;
        mid=(l+r)>>1;
    }
    printf("%lld\n",ans);
    return 0;
}

\(PS\)：暴力转树根真好用。