Description
Solution
用什么
首先，他需要把n个点连接起来且只用n-1条边，还要使总边权和最小，那么很明显是最小生成树啦。
习惯用克鲁斯卡尔算法。
怎么做
不过此处有一个条件限制就是要加一条李牌的边，就是只选n-2条王牌的边。
那么很显然的是这n-2条边是在最小生成树上的边。
所以先建立最小生成树。
那么我们只要枚举所有李牌的边，替换一条李牌的边或建立一条新边，例如从x到y费用z，因为要使其是一颗树，如果建立了一条新边就需要在x,y到x,y的公共祖先上删去一条王牌的边才可以，且费用要尽量的大。
那么我们在倍增求lca是也顺便用倍增的方法把最大费用的一条边及其的序号找出来即可。
注意
有一种情况是王牌的边建完最小生成树之后只有n-2条边，所以需要进行特判。
Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
#define rep(i,a) for(i=first[a];i;i=next[i])
using namespace std;
const int maxn=800007;
int i,j,k,l,t,n,m,w,e,num,x,y,z;
int fa[maxn],ans,first[maxn],next[maxn],last[maxn],tot,chang[maxn],an[maxn];
int ans1,ans2,ab[maxn],b[maxn],c[maxn],f[maxn][20],g[maxn][20],aa,q[maxn][20],xu[maxn];
int ans3[maxn],ans4,bb,deep[maxn];
struct node{
int x,y,z,d;
}a[maxn];
bool cmp(node x,node y){
return (x.z<y.z)||(x.z==y.z&&x.x<y.x)||(x.z==y.z&&x.x==y.x&&x.y<y.y);
}
int gf(int x){
if(!fa[x])return x;
fa[x]=gf(fa[x]);return fa[x];
}
void add(int x,int y,int z,int q){
last[++tot]=y;
next[tot]=first[x];
first[x]=tot;
chang[tot]=z;
xu[tot]=q;
last[++tot]=x;
next[tot]=first[y];
first[y]=tot;
chang[tot]=z;
xu[tot]=q;
}
void dfs(int x,int y){
int i,j;
f[x][0]=y;deep[x]=deep[y]+1;
rep(i,x){
if(last[i]!=y)dfs(last[i],x),g[last[i]][0]=chang[i],q[last[i]][0]=xu[i];
}
}
int lca(int x,int y){
int i,k=0;
if(deep[x]<deep[y])swap(x,y);
fod(i,19,0)if(deep[f[x][i]]>deep[y])bb=(g[x][i]>k?q[x][i]:bb),k=max(k,g[x][i]),x=f[x][i];
if(deep[x]!=deep[y])bb=(g[x][0]>k?q[x][0]:bb),k=max(k,g[x][0]),x=f[x][0];
fod(i,19,0)if(f[x][i]!=f[y][i])bb=(g[x][i]>k?q[x][i]:bb),k=max(k,g[x][i]),bb=(g[y][i]>k?q[y][i]:bb),k=max(k,g[y][i]),x=f[x][i],y=f[y][i];
if(x!=y)bb=(g[x][0]>k?q[x][0]:bb),k=max(k,g[x][0]),bb=(g[y][0]>k?q[y][0]:bb),k=max(k,g[y][0]);aa=k;
if(x!=y)return f[x][0];else return x;
}
int main(){
freopen("telephone.in","r",stdin);
freopen("telephone.out","w",stdout);
scanf("%d%d%d",&n,&w,&l);
fo(i,1,w){
scanf("%d%d%d",&k,&t,&e);if(k>t)swap(k,t);
a[++num].x=k,a[num].y=t,a[num].z=e,a[num].d=i;
}
sort(a+1,a+1+num,cmp);
fo(i,1,l){
scanf("%d%d%d",&ab[i],&b[i],&c[i]);
}
ans=0x7fffffff;
fo(i,1,num){
x=gf(a[i].x),y=gf(a[i].y);
if(x!=y){
fa[y]=x;m++;
ans2+=a[i].z;
ans3[m]=a[i].d;
add(a[i].x,a[i].y,a[i].z,a[i].d);
}
if(m==n-1)break;
}
if(m==n-2){
fo(i,1,l){
x=gf(ab[i]),y=gf(b[i]);
if(x!=y&&c[i]<ans){
ans=c[i];
ans1=i;
}
}
printf("%d\n",ans+ans2);
fo(i,1,m)printf("%d\n",ans3[i]);
printf("%d\n",ans1);
return 0;
}
dfs(1,0);
fo(j,1,19)fo(i,1,n){
f[i][j]=f[f[i][j-1]][j-1];
if(f[i][j])q[i][j]=(g[i][j-1]>g[f[i][j-1]][j-1]?q[i][j-1]:q[f[i][j-1]][j-1]);
if(f[i][j])g[i][j]=max(g[i][j-1],g[f[i][j-1]][j-1]);
}
fo(i,1,l){
int o=lca(ab[i],b[i]);
if(c[i]-aa<ans){
ans=c[i]-aa;
ans1=i;
ans4=bb;
}
}
printf("%d\n",ans2+ans);
fo(i,1,n-1){
if(ans3[i]==ans4)continue;
printf("%d\n",ans3[i]);
}
printf("%d\n",ans1);
}