1 条题解

  • 0
    @ 2026-8-9 11:30:23
    #include <bits/stdc++.h>
    #define int long long
    #define mk make_pair
    #define PII pair<int,int>
    #define FOR(i,j,k) for(int i=(j);i<=(k);++i)
    #define ROF(i,j,k) for(int i=(j);i>=(k);--i)
    #define FOI(a,b) for(auto a : b)
    #define wh while
    #define inf 0x3f3f3f3f3f3f3f3f
    #define IOS ios::sync_with_stdio(false);
    #define snd second
    #define fst first
    #define pb push_back
    #define CI const int
    #define NP namespace
    using NP std;
    int quickpow(int a,int b)
    {
    	int ans=1;
    	wh(b)
    	{
    		if(b&1)ans=ans*a;
    		a=a*a;
    		b>>=1;
    	}
    	return ans;
    }
    CI MAXN=2e5+5;
    struct e
    {
    	int u,v,c,w;
    	bool operator<(const e&o)const
    	{
    		return w<o.w;
    	}
    }ed[MAXN];
    int n,m,p,fa[MAXN],tt,hs,mn=inf;
    int fd(int x)
    {
    	return fa[x]==x?x:fa[x]=fd(fa[x]);
    }
    signed main(void)
    {
        freopen("travel.in","r",stdin);
        freopen("travel.out","w",stdout);
    	IOS
    	cin>>n>>m;
    	FOR(i,1,m)
    	{
    		cin>>ed[i].u>>ed[i].v>>ed[i].c;
    	}
    	cin>>p;
    	int mx=0;
    	FOR(i,1,m)
    	{
    		mx=max(mx,ed[i].c);
    		if(ed[i].c>p)
    		{
    			ed[i].w=ed[i].c-p;
    		}
    		else
    		{
    			ed[i].w=0;
    		}
    		if(ed[i].c>=p)
    		{
    			mn=min(mn,ed[i].c-p);
    		}
    	}
    	if(mx<p)
    	{
    		cout<<p-mx<<endl;
    		return 0;
    	}
    	sort(ed+1,ed+m+1);
    	FOR(i,1,n)
    	{
    		fa[i]=i;
    	}
    	tt=0;
    	hs=0;
    	int ct=0;
    	FOR(i,1,m)
    	{
    		int fu=fd(ed[i].u);
    		int fv=fd(ed[i].v);
    		if(fu!=fv)
    		{
    			fa[fu]=fv;
    			tt+=ed[i].w;
    			if(ed[i].c>=p)
    			{
    				hs=1;
    			}
    			ct++;
    			if(ct==n-1)
    			{
    				break;
    			}
    		}
    	}
    	if(hs)
    	{
    		cout<<tt;
    	}
    	else
    	{
    		cout<<tt+mn;
    	}
    	return false;
    }
    

    信息

    ID
    7118
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    (无)
    递交数
    49
    已通过
    9
    上传者