本文共 2234 字，大约阅读时间需要 7 分钟。
我们考虑一下这个东西怎么求解?
思考无果......
咦?
好像可以离线cdq,每一次判断一下如果这条边如果不选就直接删除,然后不确定的保留,必须选的就去确定连通性.
然后可以了?
好妙啊.cdq果然还是万金油.
#include #include #include #include #include #include #include #include #include using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=100010,Inf=1e9+10;struct node{ int u,v,w,id; bool operator<(const node b)const{ return w -Inf){ f[find(st[i].u)]=find(st[i].v); Ans+=st[i].w; } top=0; for(int i=1;i<=z;i++) if(find(tmp[i].u)!=find(tmp[i].v)){ st[++top]=tmp[i]; c[tmp[i].id]=top; st[top].u=find(tmp[i].u); st[top].v=find(tmp[i].v); } z=top;for(int i=1;i<=top;i++)tmp[i]=st[i];}void Solve2(int &z){ init(z);sort(&tmp[1],&tmp[z+1]);int top=0; for(int i=1;i<=z;++i) if(find(tmp[i].u)!=find(tmp[i].v)) f[find(tmp[i].u)]=find(tmp[i].v),st[++top]=tmp[i],c[tmp[i].id]=top; else if(tmp[i].w>=Inf)st[++top]=tmp[i],c[tmp[i].id]=top; z=top;for(int i=1;i<=top;++i)tmp[i]=st[i];}void cdq(int l,int r,int dep,ll Ans){ if(l==r)W[q[l].x]=q[l].w; int z=siz[dep],mid=(l+r)>>1; for(int i=1;i<=z;i++)e[dep][i].w=W[e[dep][i].id]; for(int i=1;i<=z;i++)tmp[i]=e[dep][i],c[tmp[i].id]=i; if(l==r){ init(z);sort(tmp+1,tmp+z+1); for(int i=1;i<=z;i++) if(find(tmp[i].u)!=find(tmp[i].v)){ f[find(tmp[i].u)]=find(tmp[i].v);Ans+=tmp[i].w; } ans[l]=Ans;return; } for(int i=l;i<=r;i++)tmp[c[q[i].x]].w=-Inf; Solve1(z,Ans); for(int i=l;i<=r;i++)tmp[c[q[i].x]].w=+Inf; Solve2(z); for(int i=1;i<=z;i++)e[dep+1][i]=tmp[i];siz[dep+1]=z; cdq(l,mid,dep+1,Ans);cdq(mid+1,r,dep+1,Ans);}int main(){ int n,m,Q; n=gi();m=gi();Q=gi(); for(int i=1;i<=m;i++)E[i].u=gi(),E[i].v=gi(),E[i].w=gi(),E[i].id=i; for(int i=1;i<=Q;i++)q[i].x=gi(),q[i].w=gi(); for(int i=1;i<=m;i++)W[i]=E[i].w; for(int i=1;i<=m;i++)e[0][i]=E[i]; siz[0]=m;cdq(1,Q,0,0); for(int i=1;i<=Q;i++)printf("%lld\n",ans[i]); return 0;}
转载于:https://www.cnblogs.com/mle-world/p/10320729.html