QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#721356 | #5548. Increase the Toll Fees | subarudesu# | TL | 1ms | 7800kb | C++14 | 1.7kb | 2024-11-07 15:55:59 | 2024-11-07 15:56:02 |
Judging History
answer
#include<iostream>
#include<algorithm>
using namespace std;
const long long N=2e5+5;
struct node{
long long u,v,w,used,z;
}edge[N];
bool cmp(node x,node y){
return x.w<y.w;
}
long long n,m,fa[N],Fa[N],tot1,tot2,p[N],l=1,r;
long long finded(long long x){
if(fa[x]!=x)fa[x]=finded(fa[x]);
return fa[x];
}
long long Finded(long long x){
if(Fa[x]!=x)Fa[x]=Finded(Fa[x]);
return Fa[x];
}
int main(){
cin>>n>>m;
for(long long i=1;i<=n;++i){
fa[i]=i;Fa[i]=i;
}
for(long long i=1;i<=m;++i){
cin>>edge[i].u>>edge[i].v>>edge[i].w;
edge[i].used=0;
}
sort(edge+1,edge+m+1,cmp);
long long cnt=n-1,now=0;
while(cnt){
now++;
long long u=edge[now].u,v=edge[now].v,w=edge[now].w;
if(Finded(u)!=Finded(v)){
Fa[Finded(u)]=Finded(v);
tot1+=w;
cnt--;
edge[now].used=1;
}
}
// cout<<tot1;
cnt=n-1,now=0;
while(cnt){
now++;
if(now==m+1){
cout<<"-1";
return 0;
}
if(edge[now].used){
p[++r]=now;
continue;
}
long long u=edge[now].u,v=edge[now].v,w=edge[now].w;
if(finded(u)!=finded(v)){
fa[finded(u)]=finded(v);
tot2+=w;
cnt--;
for(long long i=l;i<=r;++i){
if(finded(edge[p[i]].u)==finded(edge[p[i]].v)){
edge[p[i]].z=w+1;
swap(p[l],p[i]);
++l;
}
}
}
}
long long ans=0;
for(long long i=1;i<=m;++i){
if(edge[i].used)ans+=edge[i].z;
}
cout<<ans-tot1;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 7728kb
input:
4 6 1 2 2 1 3 5 1 4 5 2 3 3 2 4 5 3 4 4
output:
9
result:
ok single line: '9'
Test #2:
score: 0
Accepted
time: 1ms
memory: 7796kb
input:
3 4 1 2 3 2 3 4 1 3 5 1 3 10
output:
-1
result:
ok single line: '-1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 7664kb
input:
5 10 1 2 14 1 3 14 1 4 9 1 5 15 2 3 8 2 3 10 2 4 13 3 4 8 4 5 10 4 5 15
output:
21
result:
ok single line: '21'
Test #4:
score: 0
Accepted
time: 0ms
memory: 7800kb
input:
2 1 1 2 1
output:
-1
result:
ok single line: '-1'
Test #5:
score: -100
Time Limit Exceeded
input:
29171 100000 7223 21138 270743473 5598 27967 847631606 12666 26050 847631606 75 15747 270743473 8522 12955 847631606 6069 23750 270743473 18708 22605 847631606 16814 22169 847631606 11550 27119 847631606 562 15959 847631606 9400 11110 270743473 15325 23805 270743473 19169 24404 270743473 6649 12062 ...