标签：

标题问题大意

网络有 \(n\) 个节点。
你的竞争者在一些节点之间供给了连接。竞争者供给了 \(m\) 个连接，对付供给的第 \(i\) 个连接，联通了 \(fa_i\)? 和 \(fb_i\) ，价格为 \(fw_i\)? 。
你想供给 \(k\) 个连接。（保证这些连接弗成环。）第 \(j\) 个连接联通了 \(ga_j\)? 和 \(gb_j\)? ，它们的价格还没有决定。
你想设置合适的价格，使得：

你的 \(k\) 个连接城市被顾客选择。

\(k\) 个连接的价格总和最大。

所有连接都是双向的。
输出这个最大值。如果最大值无穷大，输出 \(-1\) 。

解析

如果k个链接都要被客户选择，那么这k条边都要在最小生成树上。所以，不妨事先强制这k条边在最小生成树上，如果\(k\leq n-1\)就再从\(m\)条已知边中从小到大插手直至结构出最小生成树。接下来考虑剩下的边。由于要保证必然不在最小生成树上，那么对付这样一条边\((u,v)\)，，最小生成树上\(u\)到\(v\)的路径上的每一条边都要小于或即是\((u,v)\)的边权。可以用树链剖分维护链上最小值来实现。

代码 #include <iostream> #include <cstdio> #include <algorithm> #define int long long #define N 500002 using namespace std; const int inf=1<<30; struct SegmentTree{ int dat,add; }t[N*4]; struct Edge{ int u,v,w; }e[N]; int head[N],ver[N*2],nxt[N*2],edge[N*2],w[N],l; int n,m,k,i,fa[N],size[N],son[N],dep[N],top[N],pos[N],in[N],tim; bool vis[N]; int read() { char c=getchar(); int w=0; while(c<'0'||c>'9') c=getchar(); while(c<='9'&&c>='0'){ w=w*10+c-'0'; c=getchar(); } return w; } void insert(int x,int y,int z) { l++; ver[l]=y; edge[l]=z; nxt[l]=head[x]; head[x]=l; } int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; } int my_comp(const Edge &x,const Edge &y) { return x.w<y.w; } void Kruskal() { int cnt=n-k; sort(e+1,e+m+1,my_comp); for(int i=1;i<=m;i++){ if(cnt==1) break; int f1=find(e[i].u),f2=find(e[i].v); if(f1!=f2){ fa[f1]=f2; insert(e[i].u,e[i].v,e[i].w); insert(e[i].v,e[i].u,e[i].w); vis[i]=1; cnt--; } } } void dfs1(int x,int pre) { fa[x]=pre; dep[x]=dep[pre]+1; size[x]=1; for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y!=pre){ w[y]=edge[i]; dfs1(y,x); size[x]+=size[y]; if(size[y]>size[son[x]]) son[x]=y; } } } void dfs2(int x,int t) { top[x]=t; in[x]=++tim; pos[tim]=x; if(son[x]) dfs2(son[x],t); for(int i=head[x];i;i=nxt[i]){ int y=ver[i]; if(y!=fa[x]&&y!=son[x]) dfs2(y,y); } } void update(int p) { t[p].dat=max(t[p*2].dat,t[p*2+1].dat); } void spread(int p) { if(t[p].add){ if(t[p].add<t[p*2].dat) t[p*2].dat=t[p*2].add=t[p].add; if(t[p].add<t[p*2+1].dat) t[p*2+1].dat=t[p*2+1].add=t[p].add; t[p].add=0; } } void build(int p,int l,int r) { if(l==r){ t[p].dat=w[pos[l]]; return; } int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); update(p); } void change(int p,int l,int r,int ql,int qr,int x) { if(ql<=l&&r<=qr){ if(x<t[p].dat) t[p].dat=t[p].add=x; return; } int mid=(l+r)/2; spread(p); if(ql<=mid) change(p*2,l,mid,ql,qr,x); if(qr>mid) change(p*2+1,mid+1,r,ql,qr,x); } int ask(int p,int l,int r,int x) { if(l==r) return t[p].dat; int mid=(l+r)/2; spread(p); if(x<=mid) return ask(p*2,l,mid,x); return ask(p*2+1,mid+1,r,x); } void Change(int u,int v,int w) { while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); change(1,1,n,in[top[u]],in[u],w); u=fa[top[u]]; } if(u==v) return; if(dep[u]>dep[v]) swap(u,v); change(1,1,n,in[u]+1,in[v],w); } signed main() { n=read();k=read();m=read(); for(i=1;i<=n;i++) fa[i]=i; for(i=1;i<=k;i++){ int u=read(),v=read(); insert(u,v,inf); insert(v,u,inf); fa[find(u)]=find(v); } for(i=1;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].w=read(); Kruskal(); dfs1(1,0);dfs2(1,1); build(1,1,n); for(i=1;i<=m;i++){ if(!vis[i]) Change(e[i].u,e[i].v,e[i].w); } int ans1=0,ans2=0; for(i=2;i<=n;i++){ int tmp=ask(1,1,n,in[i]); if(tmp==inf){ puts("-1"); return 0; } ans1+=tmp; } for(i=1;i<=m;i++){ if(vis[i]) ans2+=e[i].w; } printf("%lld\n",ans1-ans2); return 0; }

[CF1023F] Mobile Phone Network