CF733F Drivers Dissatisfaction 题解

Yet Another Div2f.

duel 题。

简单题目。首先肯定是只能在一条边上操作的。然后就相当于钦定一条边的最小生成树。相当于减去原最小生成树上 $u,v$ 路径中的最大值。考虑直接 kruskal 重构树解决。

// Problem: Drivers Dissatisfaction
// URL: https://www.luogu.com.cn/problem/CF733F
// Writer: WRuperD
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e18;
const int mininf = 1e9 + 7;
#define int long long
#define pb emplace_back
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void write(int x){if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0');}
#define put() putchar(' ')
#define endl puts("")
const int MAX = 2e5 + 10;

struct node{
	int u, v, w, w2;
	int id;
}; node edg[MAX];


int psz;
int fa[MAX * 4];
int val[MAX * 4], val2[MAX * 4];

int find(int x){
	if(fa[x] == x)	return x;
	return fa[x] = find(fa[x]);
}

vector <int> g2[MAX * 10];

int fat[MAX * 4], siz[MAX * 4], son[MAX * 4];
int dep[MAX * 4];
void dfs(int u){
	siz[u] = 1;
	for(int v : g2[u]){
		fat[v] = u, dep[v] = dep[u] + 1;
		dfs(v);
		siz[u] += siz[v];
		if(siz[son[u]] < siz[v])	son[u] = v;
	}
}

int top[MAX];

void dfs2(int u, int topu){
	top[u] = topu;
	if(son[u])	dfs2(son[u], topu);
	for(int v : g2[u]){
		if(v != son[u])	dfs2(v, v);
	}
}

int lca(int u, int v){
	while(top[u] != top[v]){
		if(dep[top[u]] < dep[top[v]])	swap(u, v);
		u = fat[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}
bool cmp(node x, node y){
	if(x.w != y.w){
		return x.w < y.w;
	}
	return x.w2 < y.w2;
}

bool vis[MAX];

void solve(){
	int n = read(), m = read();
	for(int i = 1; i <= m; i++){
		edg[i].w = read();
		edg[i].id = i;
	}	
	for(int i = 1; i <= m; i++){
		edg[i].w2 = read();
	}
	for(int i = 1; i <= m; i++){
		edg[i].u = read(), edg[i].v = read();
	}
	sort(edg + 1, edg + m + 1, cmp);
	for(int i = 1; i <= n; i++)	fa[i] = i;
	psz = n;
	int ans = 0;
	for(int i = 1; i <= m; i++){
		if(find(edg[i].u) == find(edg[i].v))	continue;
		vis[i] = 1;
		ans += edg[i].w;
		g2[++psz].pb(find(edg[i].u));	
		g2[psz].pb(find(edg[i].v));	
		fa[find(edg[i].u)] = fa[find(edg[i].v)] = psz;
		fa[psz] = psz;
		val[psz] = edg[i].w;
		val2[psz] = i;
	}
	int S = read();
	// write(S), endl;
	int rt = find(1);
	dfs(rt);
	dfs2(rt, rt);
	int realans = inf;
	// write(ans), endl;
	int mk = 0;
	for(int i = 1; i <= m; i++){
		int now = ans;
		if(vis[i]){
			// write(edg[i].w), put(), write(edg[i].w2), endl;
			now -= S / edg[i].w2;
			// write(now), endl;
			if(realans > now){
				realans = now;
				mk = i;
			}
			// ans = min(ans, now);
		}else{
			now -= val[lca(edg[i].u, edg[i].v)];
			// write(lca(edge))
			now += edg[i].w;
			now -= S / edg[i].w2;
			// write(now), endl;
			if(realans > now){
				realans = now;
				mk = i;
			}
		}
	}
	write(realans), endl;
	if(vis[mk]){
		for(int i = 1; i <= m; i++){
			if(vis[i]){
			write(edg[i].id), put();
				if(i == mk){
					write(edg[i].w - S / edg[i].w2), endl;
				}else{
					write(edg[i].w), endl;
				}
			}
		}
		return ; 
	}
	vis[val2[lca(edg[mk].u, edg[mk].v)]] = 0;
	for(int i = 1; i <= m; i++){
		if(vis[i]){
			write(edg[i].id), put();
			if(i == mk){
				write(edg[i].w - S / edg[i].w2), endl;
			}else{
				write(edg[i].w), endl;
			}
		}
		if(i == mk){
			write(edg[i].id), put();
			if(i == mk){
				write(edg[i].w - S / edg[i].w2), endl;
			}else{
				write(edg[i].w), endl;
			}
		}
	}
	return ;
}

signed main(){
	int t = 1;
	while(t--)	solve();
	return 0;
}