题目大意
网络有 (n) 个节点。
你的竞争者在一些节点之间提供了连接。竞争者提供了 (m) 个连接，对于提供的第 (i) 个连接，联通了 (fa_i) 和 (fb_i) ，价格为 (fw_i) 。
你想提供 (k) 个连接。（保证这些连接不成环。）第 (j) 个连接联通了 (ga_j) 和 (gb_j) ，它们的价格还没有决定。
你想设置合适的价格，使得：
- 你的 (k) 个连接都会被顾客选择。
- (k) 个连接的价格总和最大。
所有连接都是双向的。
输出这个最大值。如果最大值无穷大，输出 (-1) 。
解析
如果k个链接都要被客户选择，那么这k条边都要在最小生成树上。所以，不妨先强制这k条边在最小生成树上，如果(kleq 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
",ans1-ans2);
return 0;
}