1 条题解
-
0
#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
- 上传者