Problem - 1468J - Codeforces(最小生成树)

Problem - 1468J - Codeforces

题目大意:给定你一张连通图,你需要将它删边成一棵树,并且这棵树的所有边权都要小于等于$k$,且至少有一条边的边权为k.

解题思路:首先可以我们分析怎么去生成树是较优解.
当边权$e_i>k$时,此时如果需要这条边,那么这条边就一定要花费$c_i=e_i-k$.
当边权$e_i\le k$时,此时如果需要这条边,那么这条边的花费有两种情况: $0$或者$c_i=k-e_i$.
那已知这种贪心策略，我们优先把所有$e_i\le k$的边先连接起来，如果此时已经构成了一棵生成树，那么我们就去所有的边里找一条边权与$k$相差最小的边，然后连接这条边，取消前面的某一条边，重新构成生成树。
如果当前无法构成生成树，那么证明额外的花费是必须的，这时把最小生成树跑一遍就是正解。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
const int MAXN = 2e5+5;
const int MAXE = 2e5+5;
int par[MAXN];
int n, m, k;
struct edge{
    int from, to, cost;
}edges[MAXE];

void init(int n){
    for (int i = 1; i <= n; ++i)par[i]=i;
}

int find(int a){
    if (a == par[a])return a;
    else return par[a] = find(par[a]);
}

void unite(int a, int b){
    a=find(a), b=find(b);
    par[a]=b;
}

bool cmp(const edge& a,const edge& b){
    return a.cost < b.cost;
}

bool isSame(int a, int b){
    return find(a) == find(b);
}

ll Krisu(){
    sort(edges+1, edges+m+1, cmp);
    init(n);
    int tot = 1;
    ll res = 0;
    int mind = 1e9;
    for(int i = 1; i <=m; ++i){
        edge e = edges[i];
        if (!isSame(e.from, e.to)){
            unite(e.from, e.to);
            if (e.cost>k)res += e.cost-k;
            tot++;
            if(tot == n)break;
        }
    }
    for (int i = 1; i <= m; ++i){
        mind=min(mind, abs(edges[i].cost-k));
    }
    if (res==0)return mind;
    return res;
}

void solve(){
    cin>>n>>m>>k;
    init(n);
    int tar1 = 0, tar2 = 0, mind1 = 1e9, mind2 = 1e9;
    edge now1, now2;
    for (int i = 1; i <= m; ++i){
        cin>>edges[i].from>>edges[i].to>>edges[i].cost;
    }
    cout << Krisu() << "\n";
}

int main(){
    syncfalse
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    #endif
    int t;
    cin>>t;
    for (;t;--t){
        solve();
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80