题目链接：传送门

Description

给一张n个点m条边的连通图，每条边(ai,bi)有一个权值wi和费用ci，表示这条边每降低1的权值需要ci的花费。现在一共有S费用可以用来降低某些边的权值（可以降到负数），求图中的一棵权值和最小的生成树并输出方案。

Solution

显然S都要用到一条边上。 那么我们先跑一次最小生成树，顺便用倍增更新一遍最大值。 然后枚举每一条边，如果这条边在最小生成树里的话就直接更新答案， 否则求一遍这条边的两个顶点在树中所经过边的最大值，替换后更新答案即可

Code

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 200000 + 10, Maxm = 400000 + 100, inf = 0x3f3f3f3f;

int Vis[Maxm];

struct MAX
{
    int x, y;
}Max[Maxn][21];

struct node
{
    int x, y, w, id, c;
}A[Maxn];

inline int cmp (node a, node b)
{
    return a.w < b.w;
}

int N, M, C[Maxn];
int e, Begin[Maxn], To[Maxm], Next[Maxm], W[Maxm], ID[Maxm];
int anc[Maxn][21];
int fa[Maxn], deep[Maxn];

inline void add_edge (int x, int y, int z, int k)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e] = z;
    ID[e] = k;
}

inline int find (int x)
{
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}

inline MAX max (MAX a, MAX b)
{
    if (a.x > b.x) return a;
    return b;
}

inline void dfs (int x)
{
    for (int i = 1; i <= 20; ++i) anc[x][i] = anc[anc[x][i - 1]][i - 1], Max[x][i] = max(Max[x][i - 1], Max[anc[x][i - 1]][i - 1]);
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == anc[x][0]) continue;
        anc[y][0] = x;
        Max[y][0].x = W[i];
        Max[y][0].y = ID[i];
        deep[y] = deep[x] + 1;
        dfs(y);
    }
}

inline MAX Lca (int x, int y)
{
    MAX Ans = (MAX){0, 0};
    if (deep[x] < deep[y]) swap(x, y);
    for (int i = 20; i >= 0; --i)
        if (deep[anc[x][i]] >= deep[y])
            Ans = max(Ans, Max[x][i]), x = anc[x][i];
    if (x == y) return Ans;

    for (int i = 20; i >= 0; --i)
        if (anc[x][i] != anc[y][i])
            Ans = max(Ans, max(Max[x][i], Max[y][i])), x = anc[x][i], y = anc[y][i];

    Ans = max(Ans, max(Max[x][0], Max[y][0]));
    return Ans;
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    int K;
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= M; ++i) scanf("%d", &A[i].w);
    for (int i = 1; i <= M; ++i) scanf("%d", &A[i].c);
    for (int i = 1; i <= N; ++i) fa[i] = i;
    for (int i = 1; i <= M; ++i)
        scanf("%d%d", &A[i].x, &A[i].y), A[i].id = i;
    sort(A + 1, A + M + 1, cmp);

    int cnt = 0;
    int Sum = 0;
    for (int i = 1; i <= M; ++i)
    {
        int fx = find(A[i].x), fy = find(A[i].y);
        if (fx == fy) continue;
        Vis[i] = 1;
        add_edge (A[i].x, A[i].y, A[i].w, i);
        add_edge (A[i].y, A[i].x, A[i].w, i);
        Sum += A[i].w;
    //  add_edge (fx, fy, A[i].z);
    //  add_edge (fy, fx, A[i].z);
        fa[fy] = fx;
        ++cnt;
        if (cnt == N - 1) break;
    }

    dfs(1);

    scanf("%d", &K);
    int Ans = inf;

    int type = 0, id1 = 0, id2 = 0;
    for (int i = 1; i <= M; ++i)
    {
        if (Vis[i])
        {
            //cout<<i<<" *"<< Sum - K / A[i].c<<endl;
            if ((Sum - K / A[i].c) < Ans)
            {
                Ans = Sum - K / A[i].c;
                type = 0, id1 = i;
            }
        }
        else
        {
            MAX tmp = Lca(A[i].x, A[i].y);
            //cout<<A[i].x<<" "<<A[i].y<<" | "<<tmp.x<<" "<<tmp.y<<endl;
            //cout<<i<<" *"<< Sum - tmp.x + A[i].w - K / A[i].c<<endl;
            if ((Sum - tmp.x + A[i].w - K / A[i].c) < Ans)
            {
                Ans = Sum - tmp.x + A[i].w - K / A[i].c;
                type = 1, id1 = i, id2 = tmp.y; 
            }
        }
    }
    //cout<<type<<" "<<id1<<" "<<id2<<endl;

    if (!type) A[id1].w -= K / A[id1].c;
    else Vis[id1] = 1, A[id1].w -= K / A[id1].c, Vis[id2] = 0;

    cout<<Ans<<endl;
    for (int i = 1; i <= M; ++i)
        if (Vis[i])
            printf("%d %d\n", A[i].id, A[i].w);
    return 0;
}