QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#721356#5548. Increase the Toll Feessubarudesu#TL 1ms7800kbC++141.7kb2024-11-07 15:55:592024-11-07 15:56:02

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 15:56:02]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:7800kb
  • [2024-11-07 15:55:59]
  • 提交

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 ...

output:


result: