【问题描述】

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

【输入描述】

第一行两个整数 n，m。 第二行 m 个整数 wi，表示每条边的权值。 第三行 m 个整数 ci，表示这条边每降低 1 的权值需要 ci 的花费 接下来 m 行，每行两个整数 ai,bi，表示 ai 到 bi 有边 最后一行一个整数 S

【输出描述】

求在代价不超过 S 的情况下，最终图中最小生成树权值和最小是多少。 输出最终在最小生成树中的边的编号，以及每条边的权值。

分析

首先我们最后一定是把所有的花费用在一条边上面。
假设我们已经求出了最小生成树， c i c_i ci​ 最小值为 m i n c minc minc，那么花费一定都是在这条边上。
现在我们枚举不在树上的边，会和原来那棵树形成一个环，由于这条边本来不在最小生成树上，所以如果这条边最终在最小生成树上，一定是把所有花费都用在这条边上了，然后取代了环上最大的边。然后就倍增求环上最大边的编号和值就可以了，每次如果替换后答案更小，就记录换上的边和环上最大边（要取代的边）就可以了。

代码如下

#include <bits/stdc++.h>
#define N 200005
#define inf 2147483647
#define LL long long
using namespace std;
struct node{
	int a, b, c, w, i, n;
	bool operator < (const node & A) const{
		if(w != A.w) return w < A.w;
		return c < A.c;
	}
}d[N * 2], e[N];
int h[N], f[N], vis[N], dep[N], val[N][20], st[N][20], fa[N], C[N], W[N], cnt, minc = inf;
LL ans, sum, ans1, z = 1;
int p[2], edg[N][20];
void cr(int a, int b, int c, int i){
	d[++cnt].a = a; d[cnt].b = b; d[cnt].c = c; d[cnt].i = i; d[cnt].n = h[a]; h[a] = cnt;
}
int find(int x){
	return x == f[x]? x: f[x] = find(f[x]);
}
void dfs(int a){
	int i, b, c;
	for(i = h[a]; i; i = d[i].n){
		b = d[i].b; c = d[i].c;
		if(b == fa[a]) continue;
		fa[b] = a;
		st[b][0] = a;
		edg[b][0] = d[i].i;
		val[b][0] = c;
		dep[b] = dep[a] + 1;
		dfs(b);
	}
}
node getv(int a, int b){
	int i, c, maxn = 0, id;
	node t;
	if(dep[a] < dep[b]) swap(a, b);
	c = dep[a] - dep[b];
	for(i = 19; i >= 0; i--){
		if((1 << i & c)){
			if(maxn < val[a][i]){
				maxn = val[a][i];
				id = edg[a][i];
			}
			a = st[a][i];
		}
	}
	for(i = 19; i >= 0; i--){
		if(st[a][i] != st[b][i]){
			if(maxn < val[a][i]){
				maxn = val[a][i];
				id = edg[a][i];
			}
			if(maxn < val[b][i]){
				maxn = val[b][i];
				id = edg[b][i];
			}
			a = st[a][i];
			b = st[b][i];
		}
	}
	if(maxn < val[a][0]){
		maxn = val[a][0];
		id = edg[a][0];
	}
	if(maxn < val[b][0]){
		maxn = val[b][0];
		id = edg[b][0];
	}
	t.w = maxn; t.i = id;
	return t;
}
int main(){
	int i, j, n, m, a, b, c, w, s, hhh;
	node t;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= m; i++) scanf("%d", &W[i]);
	for(i = 1; i <= m; i++) scanf("%d", &C[i]);
	for(i = 1; i <= m; i++){
		scanf("%d%d", &e[i].a, &e[i].b);
		e[i].c = C[i], e[i].w = W[i]; e[i].i = i;
	}
	sort(e + 1, e + m + 1);
	scanf("%d", &s);
	for(i = 1; i <= n; i++) f[i] = i;	
	for(i = 1; i <= m; i++){
		a = e[i].a, b = e[i].b, c = e[i].c, w = e[i].w;
		if(find(a) != find(b)){
			if(minc > c){
				minc = c;
				hhh = e[i].i;
			}
			sum += w;
			f[find(b)] = find(a);
			vis[i] = 1;
			cr(a, b, w, e[i].i);
			cr(b, a, w, e[i].i);
		}
	}
	ans = sum - s / minc;
	dfs(1);
	for(i = 1; i <= 19; i++){
		for(j = 1; j <= n; j++){
			st[j][i] = st[st[j][i - 1]][i - 1];
			if(val[j][i - 1] >= val[st[j][i - 1]][i - 1]){
				val[j][i] = val[j][i - 1];
				edg[j][i] = edg[j][i - 1];
			}
			else{
				val[j][i] = val[st[j][i - 1]][i - 1];
				edg[j][i] = edg[st[j][i - 1]][i - 1];
			}
		}
	}
	for(i = 1; i <= m; i++){
		if(vis[i]) continue;
		a = e[i].a, b = e[i].b, c = e[i].c, w = e[i].w;
		if(c >= minc) continue;
		t = getv(a, b);
		ans1 = sum - (LL)t.w + (LL)w - (LL)s / c;
		if(ans > ans1){
			p[0] = t.i;
			hhh = e[i].i;
			ans = ans1;
		}
	}
	printf("%lld\n", ans);
	for(i = 1; i <= m; i++){
		if(e[i].i == p[0]) continue;
		if(e[i].i == hhh) printf("%d %d\n", e[i].i, e[i].w - s / e[i].c);
		else if(vis[i]) printf("%d %d\n", e[i].i, e[i].w);
	}
	return 0;
}