Description 给出n个点m条边，每条边有边权，第i条边边权为w[i]，可以花费c[i]使得第i条边边权减一，在花费不超过S的情况下求最小生成树 Input 第一行两个整数n和m分别表示点数和边数，之后m个整数w[i]表示第i条边的边权，之后m个整数c[i]表示减少第i条边单位边权需要的花费，之后m行每行两个整数u和v表示u和v之间有一条边，最后一行一整数S表示总花费(2<=n<=2e5,n-1<=m<=2e5,1<=w[i],c[i]<=1e9,0<=S<=1e9) Output 输出最小生成树权值和，然后输出每条树边的编号和边权 Sample Input 6 9 1 3 1 1 3 1 2 2 2 4 1 4 2 2 5 3 1 6 1 2 1 3 2 3 2 4 2 5 3 5 3 6 4 5 5 6 7 Sample Output 0 1 1 3 1 6 1 7 2 8 -5 Solution 必然是要把所有钱都用来减一条边更优，首先求一遍MST，那么花费要用来减树边中c[i]最小的那条边，之后如果要减去一条非树边u-v的边权使得其成为之后新图的MST中一条边的话，那就要删去原MST中u-v之间路径中边权最大值才能保证之后的新MST边权和尽量小，所以用在线倍增法维护树上边权最小值，之后枚举每条非树边考虑全部减掉其边权来更新最优解即可 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define maxn 222222 struct node { int u,v,w,id; bool operator<(const node&b)const { return w<b.w; } }edge[maxn]; int T,n,m,fa[maxn],W[maxn],C[maxn]; int pos,vis[maxn],deep[maxn],p[maxn][21],Max[maxn][21]; ll S,ans; typedef pair<int,int>P; vector<P>G[maxn]; void add(int u,int v,int id) { G[u].push_back(P(v,id)),G[v].push_back(P(u,id)); } int find(int x) { if(fa[x]==x) return x; return fa[x]=find(fa[x]); } ll kruskal(int n,int m) { for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=n;i++)G[i].clear(); int cnt=0,temp=2000000000; ll ans=0; sort(edge+1,edge+m+1); for(int k=1;k<=m;k++) { int u=edge[k].u,v=edge[k].v,w=edge[k].w,id=edge[k].id; int x=find(u),y=find(v); if(x!=y) { cnt++; fa[x]=y; ans+=w; if(temp>C[id])temp=C[id],pos=id; add(u,v,id); vis[id]=1; if(cnt==n-1)return ans; } } return -1; } void dfs(int u,int f,int w) { deep[u]=deep[f]+1,p[u][0]=f,Max[u][0]=w; for(int i=1;i<=20;i++) { if(deep[u]-(1<<i)<=0)break; int v=p[u][i-1]; p[u][i]=p[v][i-1]; if(W[Max[u][i-1]]<W[Max[v][i-1]])Max[u][i]=Max[v][i-1]; else Max[u][i]=Max[u][i-1]; } for(int i=0;i<G[u].size();i++) { int v=G[u][i].first,w=G[u][i].second; if(v!=f)dfs(v,u,w); } } int get_max(int x,int y) { if(deep[x]<deep[y])swap(x,y); int temp=0,ans=0; for(int i=20;i>=0;i--) if(deep[x]-(1<<i)>=deep[y]) { if(W[Max[x][i]]>temp)ans=Max[x][i],temp=W[ans]; x=p[x][i]; } if(x==y)return ans; for(int i=20;i>=0;i--) if(deep[x]-(1<<i)>0&&p[x][i]!=p[y][i]) { if(W[Max[x][i]]>temp)ans=Max[x][i],temp=W[ans]; if(W[Max[y][i]]>temp)ans=Max[y][i],temp=W[ans]; x=p[x][i],y=p[y][i]; if(x==y)break; } if(W[Max[x][0]]>temp)ans=Max[x][0],temp=W[ans]; if(W[Max[y][0]]>temp)ans=Max[y][0],temp=W[ans]; return ans; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++)scanf("%d",&W[i]); for(int i=1;i<=m;i++)scanf("%d",&C[i]); for(int i=1;i<=m;i++) { scanf("%d%d",&edge[i].u,&edge[i].v); edge[i].w=W[i],edge[i].id=i; } memset(vis,0,sizeof(vis)); ll sum=kruskal(n,m); scanf("%I64d",&S); ans=sum-S/C[pos]; deep[0]=0; dfs(1,0,0); int del=0; for(int i=1;i<=m;i++) { int u=edge[i].u,v=edge[i].v,id=edge[i].id; if(vis[id])continue; int t=get_max(u,v); if(t==0)continue; ll temp=sum-W[t]+W[id]-S/C[id]; if(temp<ans)ans=temp,pos=id,del=t; } if(del)vis[del]=0,vis[pos]=1; printf("%I64d\n",ans); W[pos]-=S/C[pos]; for(int i=1;i<=m;i++) if(vis[i]) printf("%d %d\n",i,W[i]); return 0; }