题意简述
给定一张无向图和两个权值G、S，图中每条边有两个权值au,ag，求一棵生成树，设树边中最大的权值au为A，最大的权值ag为B，需使下式最小化：G*A+S*B。
算法概述
【暴力】
该题要求一棵特殊的最小生成树，显然Kruskal无法直接求出有二维权值限制的最小生成树，所以我们考虑先固定一维。
然后依次枚举每条边，令A等于当前的au，则au固定，再以权值ag为关键字进行Kruskal，最终必然能够求出答案。Kruskal过程中注意，假设当前枚举的边即为最终的树边中权值au最大者，那么则其余边的权值au必然小于等于之，，则可直接筛去权值au大于之者。
时间复杂度O(m2logm)。
【正解】
暴力算法的瓶颈主要在于Kruskal上。我们发现，当前枚举的au为答案的A时，则剩余的树边的权值au必然小于等于之，所以可以想到先以权值au为关键字升序排序，然后开始枚举每条边，固定au，此时我们进行Kruskal时，无需枚举所有的边，由于答案的树边的au必然小于当前边的au，所以直接在排在当前边之前的边中找答案即可。
那么考虑维护一个栈，以au为关键字枚举时将该边压入栈中，每次压栈时维护栈中以ag为关键字的单调性，便可省去Kruskal的排序操作。然后以此枚举栈中的边，进行Kruskal，将每一轮Kruskal选出的所有边覆盖到栈中，将栈刷新，即可保证栈中最多只有n-1个元素。
如此，可维持时间复杂度在O(nm)。
参考代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=210,M=5e4+10;
const ll INF=9223372036854775807;
struct Edge{
int u,v,au,ag;
bool operator <(const Edge &E)const
{
if(au!=E.au)return au<E.au;
return ag<E.ag;
}
}edge[M],stk[M];
int top;
int fa[N];
int n,m,G,S;
ll ans=INF;
int get(int x)
{
if(fa[x]==x)return fa[x];
return fa[x]=get(fa[x]);
}
int main()
{
scanf("%d%d%d%d",&n,&m,&G,&S);
for(int i=1;i<=m;i++)
scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].au,&edge[i].ag);
sort(edge+1,edge+m+1); //以au为关键字升序排序
for(int i=1;i<=m;i++)
{
stk[++top]=edge[i]; //压栈
for(int j=top;j>=2;j--)
if(stk[j].ag<stk[j-1].ag)swap(stk[j],stk[j-1]); //维护栈中元素的以ag为关键字的单调性。该步骤代替了原Kruskal中的排序操作，降低了时间复杂度。
int cnt=0;
for(int i=1;i<=n;i++)fa[i]=i;
for(int j=1;j<=top;j++) //栈中元素以ag为关键字单调上升，故而可直接按序枚举
{
int u=get(stk[j].u),v=get(stk[j].v);
if(u==v)continue;
fa[u]=v;
stk[++cnt]=stk[j]; //覆盖栈中元素，剔除无用边
if(cnt==n-1)break; //最多n-1条树边
}
if(cnt==n-1) //更新答案
ans=min(ans,(ll)G*edge[i].au+(ll)S*stk[cnt].ag);
//此处不能直接break，因为可能后面还有更小的ag值未被枚举到。要考虑所有方案中的最小值。
top=cnt;
}
if(ans==INF)printf("-1
");
else printf("%lld
",ans);
return 0;
}