给你很多条边,每条边有一个初始边权w1,然后还有一个值表示把这个边权减一的代价w2,然后给你一个预算budget,然后让你输出怎么选边之后构成的树的边权和最小(在用budget减少了边权之后),输出你选的每一条边以及该边此时的边权.
思路:首先显然预算都要用到你选的那棵树上w2最小的那条边上,然后就看你怎么选树,我的思路是:先prime选出最小生成树并记录现在的边上最小的w2,然后树链剖分,用线段树记录路径上边的边权的最大值.然后把所有的边按w2排序,当还有边的w2小于记录的最小的w2的时候,求出把这条边加进去并把形成的环上w1最大的那个边去掉能得到的答案,和之前的答案进行比较,从而找出最优的,由于最小生成树其实可能有很多种不同的我并不能保证我的思路对,但是考虑到最小生成树其实还是比较特殊的,可以推测不同的最小生成树得到的答案是一样的,我就这么做了,果然对了.
写道后面感觉好烦,就特别暴力了一下,反正后面的那部分耗时不大.
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define MAXN 200010 //节点数目
using namespace std;
typedef long long ll; vector<pair<int,int> >v[MAXN];
int fa[MAXN];
int deg[MAXN];
int num[MAXN];
int son[MAXN];
int top[MAXN];
int w[MAXN];//每个和对应子节点相连的边对应的编号
int tot;//边的编号
int tree[MAXN<<];
void dfs1(int s,int d)
{
deg[s]=d,num[s]=,son[s]=;
for(int i=;i<v[s].size();i++)
{
int t=v[s][i].first;
if(t==fa[s])
continue;
fa[t]=s;
dfs1(t,d+);
num[s]+=num[t];
if(num[t]>num[son[s]])
son[s]=t;
}
}
void dfs2(int s,int tp)
{
top[s]=tp;
if(son[s])
{
w[son[s]]=++tot;
dfs2(son[s],tp);
}
for(int i=;i<v[s].size();i++)
{
int t=v[s][i].first;
if(t==fa[s]||t==son[s])
continue;
w[t]=++tot;
dfs2(t,t);
}
}
void update(int le,int ri,int val,int l,int r,int n)//区间更改,在这个程序中一定有le==ri,所以退化成单点更新
{
if(l==r)
{
tree[n]=val;
return;
}
if(le<=mid)
update(le,le,val,l,mid,n<<);
else update(le,le,val,mid+,r,n<<|);
tree[n]=max(tree[n<<],tree[n<<|]);
}
int query(int le,int ri,int l,int r,int n)
{
if(le==l&&ri==r)
return tree[n];
if(ri<=mid)
return query(le,ri,l,mid,n<<);
else if(le>mid)
return query(le,ri,mid+,r,n<<|);
else return max(query(le,mid,l,mid,n<<),query(mid+,ri,mid+,r,n<<|));
}
int find(int s,int t,int n)
{
int s1=top[s],t1=top[t],ans=;
while(s1!=t1)
{
if(deg[s1]<deg[t1])
{
swap(s1,t1);
swap(s,t);
}
ans=max(ans,query(w[s1],w[s],,n,));
s=fa[s1];s1=top[s];
}
if(s!=t)
{
if(deg[s]<deg[t])
swap(s,t);
return max(ans,query(w[son[t]],w[s],,n,));
}
return ans;
}
int change(int s,int t,int c,int n)
{
int s1=top[s],t1=top[t];
while(s1!=t1)
{
if(deg[s1]<deg[t1])
{
swap(s1,t1);
swap(s,t);
}
update(w[s1],w[s],c,,n,);
s=fa[s1];s1=top[s];
}
if(s!=t)
{
if(deg[s]<deg[t])
swap(s,t);
update(w[son[t]],w[s],c,,n,);
}
}
vector<pair<int,int> >v2[MAXN];
int val1[MAXN],val2[MAXN];
bool sign[MAXN];
int nu[MAXN];
int fa2[MAXN];
set<pair<int,int> >s;
int minn=-;
ll anss=;
void prime(int t,int n)
{
sign[t]=true;
for(int i=;i<v2[t].size();i++)
{
int t2=v2[t][i].first;
if(nu[t2]&&val1[nu[t2]]>val1[v2[t][i].second])
s.erase(s.find(make_pair(val1[nu[t2]],t2)));
else if(nu[t2])
continue;
nu[t2]=v2[t][i].second;
fa2[t2]=t;
s.insert(make_pair(val1[nu[t2]],t2));
}
for(int i=;i<n;i++)
{
pair<int,int>temp=*s.begin();
s.erase(s.begin());
int t=temp.second;
sign[t]=true;
anss+=val1[nu[t]];
v[fa2[t]].push_back(make_pair(t,nu[t]));
if(minn==-||val2[nu[t]]<val2[minn])
minn=nu[t];
for(int i=;i<v2[t].size();i++)
{
int t2=v2[t][i].first;
if(sign[t2])
continue;
if(nu[t2]&&val1[nu[t2]]>val1[v2[t][i].second])
s.erase(s.find(make_pair(val1[nu[t2]],t2)));
else if(nu[t2])
continue;
nu[t2]=v2[t][i].second;
fa2[t2]=t;
s.insert(make_pair(val1[nu[t2]],t2));
}
}
}
int a,b,c;
pair<int,int>p[MAXN];
int ss[MAXN],tt[MAXN];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
scanf("%d",&val1[i]);
for(int i=;i<=m;i++)
scanf("%d",&val2[i]);
for(int i=;i<=m;i++)
{
scanf("%d%d",&a,&b);
ss[i]=a;
tt[i]=b;
v2[a].push_back(make_pair(b,i));
v2[b].push_back(make_pair(a,i));
}
int budget;
scanf("%d",&budget);
prime(,n);
fa[]=;
dfs1(,);
tot=;
dfs2(,);
for(int i=;i<=n;i++)
{
a=i;
for(int j=;j<v[i].size();j++)
{
b=v[i][j].first;
c=val1[v[i][j].second];
change(a,b,c,n-);//修改a,b之间路径值为c;
}
}
for(int i=;i<=m;i++)
{
p[i].first=val2[i];
p[i].second=i;
}
sort(p+,p++m);
int maxn=;
int fin=minn;
int fansile;
for(int i=;i<=m;i++)
{
int numb=p[i].second;
if(numb==minn)
break;
int temp=find(ss[numb],tt[numb],n-);
int curr=val1[numb]-temp;
curr-=(budget/val2[numb])-(budget/val2[minn]);
if(maxn>curr)
{
maxn=curr;
fin=numb;
fansile=temp;
}
}
if(fin==minn)
{
printf("%lld\n",anss-budget/val2[minn]);
for(int i=;i<=n;i++)
{
for(int j=;j<v[i].size();j++)
{
int numb=v[i][j].second;
if(numb==minn)
printf("%d %d\n",numb,val1[numb]-budget/val2[numb]);
else
printf("%d %d\n",numb,val1[numb]);
}
}
}
else
{
int caos=ss[fin],caot=tt[fin];
int caos2=caos,caot2=caot;
int mubiao;
while()
{
int tops=top[caos2];
int topt=top[caot2];
if(tops==topt)
{
if(deg[caos2]<deg[caot2])
mubiao=caos2;
else mubiao=caot2;
break;
}
else if(deg[tops]<deg[topt])
caot2=fa[topt];
else caos2=fa[tops];
if(caos2==caot2)
{
mubiao=caos2;
break;
}
}
bool ok=false;
int mubiao2;
while(caos!=mubiao)
{
if(val1[nu[caos]]==fansile)
{
ok=true;
mubiao2=nu[caos];
break;
}
caos=fa2[caos];
}
while(!ok&&caot!=mubiao)
{
if(val1[nu[caot]]==fansile)
{
ok=true;
mubiao2=nu[caot];
break;
}
caot=fa2[caot];
}
printf("%I64d\n",anss+maxn-budget/val2[minn]);
for(int i=;i<=n;i++)
{
for(int j=;j<v[i].size();j++)
{
if(v[i][j].second==mubiao2)
continue;
printf("%d %d\n",v[i][j].second,val1[v[i][j].second]);
}
}
printf("%d %d\n",fin,val1[fin]-budget/val2[fin]);
}
return ;
}