【問題描述】
給出一張 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;
}