NOI.AC
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #213151 | #2675. Road Reform | Invisible_H | 100 | 1469ms | 7464kb | C++ | 3.7kb | 2024-11-09 21:28:47 | 2024-11-09 23:21:27 |
answer
#include <bits/stdc++.h>
using namespace std;
const long long MX=200100,INF=0x3f3f3f3f;
long long fath[MX];
long long fnd(long long x){
if(x==fath[x]) return x;
return fath[x]=fnd(fath[x]);
}
bool merge(long long x,long long y){
long long fx=fnd(x),fy=fnd(y);
if(fx==fy) return 0;
if(rand()&1) swap(fx,fy);
fath[fx]=fy;
return 1;
}
struct node{
long long x,y,w;
}edge[MX<<1];
inline bool cmp(node a,node b){
return a.w<b.w;
}
signed main(){
long long n,m,k;scanf("%lld%lld%lld",&n,&m,&k);
for(long long i=1;i<=n;i++) fath[i]=i;
for(long long i=1;i<=m;i++){
long long x,y,w;scanf("%lld%lld%lld",&x,&y,&w);
edge[i]={x,y,w};
}
sort(edge+1,edge+1+m,cmp);
long long cnt=0,sum=0,ans=0;
for(long long i=1;i<=m;i++){
if(merge(edge[i].x,edge[i].y)){
// printf("%lld %lld\n",edge[i].x,edge[i].y);
sum++;
cnt=max(cnt,edge[i].w);
if(cnt>k)ans+=cnt-k;
if(sum==n-1) break;
}
}
if(cnt<k){
ans=0x3f3f3f3f;
for(long long i=1;i<=m;i++){
ans=min(ans,abs(k-edge[i].w));
}
}
printf("%lld\n",ans);
return 0;
}
/*
CCCCCCCCCCCCC AAA IIIIIIIIII CCCCCCCCCCCCC AAA IIIIIIIIII AAA
CCC::::::::::::C A:::A I::::::::I CCC::::::::::::C A:::A I::::::::I A:::A
CC:::::::::::::::C A:::::A I::::::::I CC:::::::::::::::C A:::::A I::::::::I A:::::A
C:::::CCCCCCCC::::C A:::::::A II::::::IIC:::::CCCCCCCC::::C A:::::::A II::::::II A:::::::A
C:::::C CCCCCC A:::::::::A I::::I C:::::C CCCCCC A:::::::::A I::::I A:::::::::A
C:::::C A:::::A:::::A I::::IC:::::C A:::::A:::::A I::::I A:::::A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::A A:::::A I::::IC:::::C A:::::A A:::::A I::::I A:::::A A:::::A
C:::::C A:::::AAAAAAAAA:::::A I::::IC:::::C A:::::AAAAAAAAA:::::A I::::I A:::::AAAAAAAAA:::::A
C:::::C A:::::::::::::::::::::A I::::IC:::::C A:::::::::::::::::::::A I::::I A:::::::::::::::::::::A
C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I C:::::C CCCCCC A:::::AAAAAAAAAAAAA:::::A I::::I A:::::AAAAAAAAAAAAA:::::A
C:::::CCCCCCCC::::C A:::::A A:::::A II::::::IIC:::::CCCCCCCC::::C A:::::A A:::::A II::::::II A:::::A A:::::A
CC:::::::::::::::C A:::::A A:::::A I::::::::I CC:::::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCC::::::::::::C A:::::A A:::::A I::::::::I CCC::::::::::::C A:::::A A:::::A I::::::::I A:::::A A:::::A
CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIII CCCCCCCCCCCCCAAAAAAA AAAAAAAIIIIIIIIIIAAAAAAA AAAAAAA
*/
详细
小提示：点击横条可展开更详细的信息
Test #1:
score: 5
Accepted
time: 0ms
memory: 1216kb
input:
20 80 10 11 10 207 8 15 45 2 9 253 10 8 91 10 14 174 20 19 272 20 3 69 4 7 9 19 12 192 3 5 21 20 1 2...
output:
651
result:
ok single line: '651'
Test #2:
score: 5
Accepted
time: 0ms
memory: 1212kb
input:
20 80 10 8 15 24 16 14 128 7 9 8 6 1 12 4 11 273 9 14 238 8 17 155 11 5 220 15 10 132 17 7 10 9 18 1...
output:
569
result:
ok single line: '569'
Test #3:
score: 5
Accepted
time: 0ms
memory: 1212kb
input:
20 80 10 1 13 196 6 2 133 11 14 193 4 11 148 11 19 21 16 15 84 3 19 201 5 15 286 11 16 161 12 13 296...
output:
633
result:
ok single line: '633'
Test #4:
score: 5
Accepted
time: 0ms
memory: 1216kb
input:
20 80 10 5 15 33 9 13 52 9 5 48 8 3 251 6 9 281 8 9 111 18 17 48 8 14 145 19 15 299 4 20 88 6 2 281 ...
output:
596
result:
ok single line: '596'
Test #5:
score: 5
Accepted
time: 0ms
memory: 1212kb
input:
20 80 10 6 15 124 7 15 242 6 5 172 11 2 46 3 4 273 2 4 173 7 9 175 9 16 264 17 14 15 16 17 211 8 18 ...
output:
989
result:
ok single line: '989'
Test #6:
score: 5
Accepted
time: 0ms
memory: 1220kb
input:
20 80 10 6 5 252 2 20 182 20 14 107 5 15 128 4 10 283 8 17 21 2 17 203 9 4 289 18 4 218 3 15 25 10 9...
output:
571
result:
ok single line: '571'
Test #7:
score: 5
Accepted
time: 47ms
memory: 3552kb
input:
2000 100000 800 1287 1255 1987 1744 883 836 149 1453 1336 351 1172 1071 850 1465 848 740 1675 863 11...
output:
6
result:
ok single line: '6'
Test #8:
score: 5
Accepted
time: 54ms
memory: 3552kb
input:
2000 100000 800 540 62 1546 684 1940 1135 506 1341 1784 1850 361 1977 18 140 1635 1651 1916 1907 199...
output:
57
result:
ok single line: '57'
Test #9:
score: 5
Accepted
time: 52ms
memory: 3552kb
input:
2000 100000 800 1450 642 1197 990 388 1850 1656 809 1402 725 786 1349 613 1059 890 1259 1575 1064 95...
output:
1
result:
ok single line: '1'
Test #10:
score: 5
Accepted
time: 52ms
memory: 3564kb
input:
2000 100000 10000000 232 194 5205389 1290 1320 94756446 1596 1172 8604877 1838 1057 38095640 1301 54...
output:
169
result:
ok single line: '169'
Test #11:
score: 5
Accepted
time: 64ms
memory: 3564kb
input:
2000 100000 10000000 1377 361 48147042 1023 1928 5049880 1696 843 14727225 920 1294 58661444 1665 51...
output:
533
result:
ok single line: '533'
Test #12:
score: 5
Accepted
time: 52ms
memory: 3564kb
input:
2000 100000 10000000 23 1840 61297021 1090 1814 98946038 1413 1691 85852947 86 1463 92991569 1268 82...
output:
230103
result:
ok single line: '230103'
Test #13:
score: 5
Accepted
time: 135ms
memory: 7460kb
input:
200000 200000 10000000 163447 52269 827108961 69433 60328 8764874 184517 157379 878957413 2825 13277...
output:
98144644196729
result:
ok single line: '98144644196729'
Test #14:
score: 5
Accepted
time: 152ms
memory: 7460kb
input:
200000 200000 10000000 26437 26449 733968315 72457 129890 760533116 45625 117585 453891083 113120 65...
output:
97982017911608
result:
ok single line: '97982017911608'
Test #15:
score: 5
Accepted
time: 155ms
memory: 7456kb
input:
200000 200000 10000000 134481 172469 958604013 187505 51187 883335613 78523 97379 748522908 76899 44...
output:
98108458217572
result:
ok single line: '98108458217572'
Test #16:
score: 5
Accepted
time: 150ms
memory: 7460kb
input:
200000 200000 10000000 31044 159067 847353551 87451 43252 982699932 138867 5542 154557540 83604 6864...
output:
98165693118564
result:
ok single line: '98165693118564'
Test #17:
score: 5
Accepted
time: 142ms
memory: 7460kb
input:
200000 200000 10000000 19846 69397 59750638 19566 101018 183206436 7465 190436 164547218 192600 1650...
output:
98270021595856
result:
ok single line: '98270021595856'
Test #18:
score: 5
Accepted
time: 149ms
memory: 7464kb
input:
200000 200000 10000000 75029 14324 856954422 6328 45799 557275111 92416 7355 61760133 58432 149196 6...
output:
98016594710576
result:
ok single line: '98016594710576'
Test #19:
score: 5
Accepted
time: 127ms
memory: 7464kb
input:
200000 200000 10000000 50062 13355 435813272 161002 4865 505414563 118169 48194 579627562 139289 413...
output:
98085543969676
result:
ok single line: '98085543969676'
Test #20:
score: 5
Accepted
time: 138ms
memory: 7460kb
input:
200000 200000 10000000 5476 97888 999474454 20665 24758 972246854 170123 118973 486801275 114106 174...
output:
97937044812669
result:
ok single line: '97937044812669'
